Official

C - On a Diet Editorial by KumaTachiRen


実際にシミュレーションします。

シミュレーションする上では直近 \(M\) 日間で食べたおやつのカロリーの総和が高速に求められればよく、差分更新すると簡潔に実装できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, M;
  long long K;
  cin >> N >> M >> K;
  vector<int> A(N);
  for (auto &v : A) cin >> v;
  long long sum = 0;
  for (int i = 0; i < N; i++) {
    if (i >= M) sum -= A[i - M];
    if (sum + A[i] <= K) {
      sum += A[i];
      cout << "Yes\n";
    } else {
      A[i] = 0;
      cout << "No\n";
    }
  }
}

実装例 (Python)

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
s = 0
for i in range(N):
  if i >= M:
    s -= A[i - M]
  if s + A[i] <= K:
    s += A[i]
    print("Yes")
  else:
    A[i] = 0
    print("No")

posted:
last update: