SRM684D1Easy CliqueParty
久しぶりの投稿。
方針
両サイドを固定すると、集合Dの最大値が決まる。
左端からk-smoothを満たすように選んで行く。
コード
class CliqueParty { public: int maxsize(vector<int> a, int k) { int N = a.size(); sort(a.begin(), a.end()); int ans = 0; FOR(l,0,N) { FOR(r,l+1,N) { ll mx = a[r] - a[l]; int alive[55]; FOR(i,l,r+1) alive[i] = true; FOR(i,l,r) { if(!alive[i]) continue; FOR(j,i+1,r+1) { if(ll(a[j]-a[i])*k<mx) { if(j == r) alive[i] = false; else alive[j] = false; } else break; } } int cnt = 0; FOR(i,l,r+1) { cnt += alive[i]; } ans = max(ans, cnt); } } return ans; } };