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;
    }
};