SRM 659 Div1 ApplesAndOrangesEasy

ほぼ1ヶ月ぶりの更新か...。久しぶりすぎてTopCoderの提出法忘れていた...。

BITかなと一瞬思ったが、リンゴを1とおくと簡単にサブリストのリンゴの数を計算できるので、事前に合計を計算してから単純に左端、右端を引いたり足したりしていくことにした。

class ApplesAndOrangesEasy {
public:
    int maximumApples(int N, int K, vector <int> info) {
        int arr[2005] = {};
        int k2 = K/2;
        for (int i : info) {
            arr[i-1]=1;
        }
        for (int i = 0; i < N; i++) {
            if (arr[i]==1)continue;
            arr[i]=1;
            int left = max(0, i-K+1);
            int right = min(N-1, i+K-1)-K+1;
            int sum = 0;
            for (int j = 0; j < K; j++) {
                sum += arr[left+j];
            }
            bool f = true;
            for (int j = left; j <= right; j++) {
                if (sum > k2){
                    f=false;
                    break;
                }
                sum -= arr[j];
                sum += arr[K+j];
            }
            if(!f)
                arr[i]=0;
        }
        int cnt =0;
        for (int i = 0; i < N; i++) {
            if (arr[i])
                cnt+=arr[i];
        }
        return cnt;
    }
};