\(K=1\) の時、各区画に\(T_i\) 回水をやることで必ず水分量を目標に一致させることができます。

以降、\(K\geq 2\) を考えます。 開始位置として \(1\) を選ぶことはちょうど \(T_1\) 回です。なぜならばそれ以外で区画 \(1\) の水が増えないからです。したがって、開始位置として \(2\) を選ぶことは \(K\geq 2\) の時は \(T_2-T_1\) 回となります。

一般に開始位置を \(i\) にする回数は \(T_i\) から \(i-K+1,\ldots,i-1\) を開始位置にする回数を引いた値です。そのため、\(1\) から順に開始位置を \(i\) にして操作する回数が特定できます。これらの回数が負になることがあった場合、一致させることは不可能です。なぜならば、先ほど導いた条件より特定の開始位置を選ぶ回数というのは一意に定まり、その一意なものが無効であるからです。これらの回数が全て非負であるならば、その構築方法が実際に目標と一致させることができるかを確認します。一致する場合のみ可能です。一致しない場合は不可能です。

実際に計算するには、前 \(K-1\) 個の開始位置の操作回数の合計を持つ必要があり、区画を一個動くごとに差分を考えると区画を \(1\) ずつインクリメントするごとに \(\mathrm{O}(1)\) で計算できることがわかります。

これを適切に実装することで、時間計算量 \(\mathrm{O}(N)\) で解くことができ正解を得られます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> t(n);
    for (auto& e : t) cin >> e;
    int now = 0;
    vector<int> use(n);
    for (int i = 0; i < n; ++i) {
        if (i - k >= 0) now -= use[i - k];
        if (i + k <= n) {
            if (t[i] < now) {
                cout << "No" << endl;
                return 0;
            }
            use[i] = t[i] - now;
            now = t[i];
        }
        if (now != t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}