この問題は階差に注目することで解くことができます。

区画 \(i\) の水分量の不足を \(C_i=B_i-A_i\) と定めます。これにより問題は次のように読み替えられます。

整数列 \(C=(C_1,\ldots,C_N)\) が与えられる。「\(i\) を選び、 \(C_i,C_{i+1},\ldots,C_{i+K-1}\) それぞれから \(1\) を引く」という操作を行って、全て \(0\) にするための最小回数は？

\(C\) が負の要素を含む場合不可能です。以下、\(C\) の全ての要素は \(0\) 以上とします。

\(C_0=C_{N+1}=0\) と定め、 \(C\) の階差数列を \(D_i=C_{i+1}-C_{i}\) \((0 \leq i \leq N)\)と定めます。 \(C\) の全ての要素が \(0\) であることは、 \(D\) の全ての要素が \(0\) であることと同値です。また、「\(i\) を選び、\(C\) の連続する \(K\) 個の要素 \(C_i,C_{i+1},\ldots,C_{i+K-1}\) それぞれから \(1\) を引く」という操作は「\(i\) を選び、\(D_i\) から \(1\) を引き、\(D_{i+K}\) に \(1\) を加える」と同値です。

例：

\(D_0\) を変更する操作は \(i=0\) しか存在しないため、 \(i=0\) で操作を行う回数は \(D_0\) から一意に定まります。その後、 \(D_1\) について考えることで、同様にして左から貪欲に操作回数が一意に決まります。各 \(i\) に対する操作は \(O(1)\) で行えるため、全体で \(O(N)\) でこの問題を解くことができます。

実装例 (C++)

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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  for(int i=0; i<n; i++) cin >> a[i];
  for(int i=0; i<n; i++) cin >> b[i];

  vector<int> c(n+2);
  for(int i=0; i<n; i++){
   c[i+1] = b[i] - a[i];
  }
  vector<long long> d(2*n);
  for(int i=0; i<=n; i++){
    d[i] = c[i+1] - c[i];
  }

  long long ans = 0;
  for(int i=0; i<n; i++){
    if(d[i] < 0){
      cout << -1 << endl;
      return 0;
    }
    ans += d[i];
    d[i+k] += d[i];
    d[i] = 0;
  }

  for(int i=0; i<2*n; i++){
    if(d[i] != 0){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = [0] + [b - a for a, b in zip(A, B)] + [0]
D = [C[i+1] - C[i] for i in range(N+1)] + ([0] * N)

ans = 0
for i in range(N):
  if D[i] < 0:
    print(-1)
    exit()
  ans += D[i]
  D[i+K] += D[i]
  D[i] = 0

if all(d==0 for d in D):
  print(ans)
else:
  print(-1)