SRM659 div.1 250 ApplesAndOrangesEasy

ApplesAndOrangesEasy.cpp

#include <bits/stdc++.h>
using namespace std;

struct ApplesAndOrangesEasy {
  int maximumApples(int N, int K, vector<int> _info) {
    vector<int> info(N, 0);
    for (int i : _info) info[i-1] = 1;
    
    for (int i = 0; i < N; i++) {
      int cnt = 0, left = max(0, i-K+1);
      for (int j = left; j < left+K; j++) cnt += info[j];
      int max_cnt = cnt;
      for (int j = left; j < min(i, N-K); j++) {
	cnt += info[j+K] - info[j];
	max_cnt = max(max_cnt, cnt);
      }
      assert(max_cnt <= K/2);
      if (max_cnt < K/2) info[i] = 1;
    }

    return count(info.begin(), info.end(), 1);
  }
};