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