Overview

This problem asks whether we can make each section’s moisture level exactly match the target value \(B_i\) from the current value \(A_i\) by repeatedly applying an operation that increases the moisture level of \(K\) consecutive sections by \(1\) each, and if possible, to find the minimum number of operations.

Analysis

Formulating the Operations

Let \(x_l\) denote the number of times we choose starting position \(l\) (\(0\)-indexed, \(0 \leq l \leq M-1\), where \(M = N - K + 1\)) for each operation. Then, the increase in moisture for section \(i\) is the sum of all operations that cover section \(i\):

\[A_i + \sum_{\max(0,\, i-K+1) \leq l \leq \min(i,\, M-1)} x_l = B_i\]

In other words, we need to satisfy this equation for all sections under the constraint that each \(x_l \geq 0\).

Greedy Approach Uniquely Determines the Solution

Looking at sections from left to right, for section \(i\) (where \(i < M\)): - Let current_sum be the sum of already determined \(x_0, x_1, \ldots, x_{i-1}\) that cover section \(i\) - To satisfy the equation, \(x_i = (B_i - A_i) - \text{current\_sum}\) is uniquely determined - If \(x_i < 0\), then it is impossible (moisture cannot be decreased)

For sections \(i \geq M\), no new operation can start, so we only need to verify whether the equation holds with existing operations alone.

Why This is Optimal

Since each \(x_l\) is uniquely determined by the equality constraints, if a solution exists, the total number of operations \(\sum x_l\) is also unique. Therefore, the existing solution is automatically the minimum solution.

Algorithm

1. Set \(M = N - K + 1\) and prepare array \(x\)
2. Scan from left to right while maintaining current_sum (the sum of operations covering the current section)
3. For each section \(i\):
   • If \(i \geq K\), then \(x_{i-K}\) no longer covers section \(i\), so subtract it from current_sum (sliding window)
   • If \(i < M\), compute \(x_i = B_i - A_i - \text{current\_sum}\). If negative, output -1 and terminate. Otherwise, add it to current_sum and to total
   • If \(i \geq M\), check whether current_sum \(= B_i - A_i\); if not, output -1
4. If all sections are processed without issues, output total

Concrete Example

For \(N=5, K=3, A=[1,2,3,4,5], B=[3,5,6,6,5]\): - Required increase \(D = B - A = [2, 3, 3, 2, 0]\) - \(i=0\): \(x_0 = 2 - 0 = 2\), current_sum\(=2\) - \(i=1\): \(x_1 = 3 - 2 = 1\), current_sum\(=3\) - \(i=2\): \(x_2 = 3 - 3 = 0\), current_sum\(=3\) - \(i=3\) (verification): subtract \(x_0=2\) from current_sum to get \(1\), which does not match \(D_3=2\) → -1

Complexity

• Time complexity: \(O(N)\) (only a single pass through the array)
• Space complexity: \(O(N)\) (for storing array \(x\))

Implementation Notes

• Sliding window: By subtracting \(x_{i-K}\) from current_sum, we can update the sum of operations covering section \(i\) in \(O(1)\)

• Overflow caution: The minimum number of operations can be up to \(3 \times 10^{14}\), so 64-bit integers are required (in Python, arbitrary precision integers are used automatically, so this is not an issue)

• Case distinction between first and second halves: Note that for \(i < M\) we determine \(x_i\), while for \(i \geq M\) we only perform verification

  Source Code

import sys
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    M = N - K + 1
    x = [0] * M
    
    current_sum = 0
    total = 0
    
    for i in range(N):
        if i >= K:
            current_sum -= x[i - K]
        if i < M:
            xi = B[i] - A[i] - current_sum
            if xi < 0:
                print(-1)
                return
            x[i] = xi
            current_sum += xi
            total += xi
        else:
            if current_sum != B[i] - A[i]:
                print(-1)
                return
    
    print(total)

solve()

---

This editorial was generated by claude4.6opus-thinking.