Overview

This problem asks us to determine whether we can make array \(A\) of length \(N\) exactly match a target array \(B\) by repeatedly applying an operation that adds \(+1\) to a contiguous subarray of length \(K\), and if possible, to find the minimum number of operations.

This can be solved efficiently by greedily determining the number of operations from the left end.

---

Analysis

1. Focus on the Difference

First, for each section \(i\) (\(1 \leq i \leq N\)), consider the required moisture increase \(D_i = B_i - A_i\). Since operations cannot decrease moisture levels, if there exists even one section where \(D_i < 0\), it is impossible to achieve the target. In this case, immediately output -1.

Hereafter, we assume \(D_i \geq 0\) for all \(i\).

2. Greedily Determine from the Left End

For the operation “add \(+1\) to \(K\) consecutive sections,” a greedy approach based on the leftmost unresolved section can be applied.

Specifically, consider section \(1\). The only operation that can cover section \(1\) is the one starting at section \(1\) (i.e., \(l=1\)). Therefore, to achieve the target for section \(1\), we must perform the operation with \(l=1\) exactly \(D_1\) times.

After this operation, the moisture levels of all sections from \(1\) to \(K\) increase by \(D_1\).

Next, consider section \(2\). Section \(2\) has already increased by \(D_1\) from the \(l=1\) operation. Therefore, the number of times \(x_2\) we should perform the operation starting at section \(2\) (\(l=2\)) is the deficit \(D_2 - D_1\). If \(D_2 - D_1 < 0\), the target value has already been exceeded, so we can determine it is impossible (-1).

3. Generalization and Optimization

Let us generalize this. Let \(x_i\) be the number of operations starting at section \(i\). If \(S\) is the total number of previous operations affecting section \(i\), then the number of new operations \(x_i\) to perform at section \(i\) is determined as follows:

• When \(i \leq N - K + 1\) (operations can be started)
  • \(x_i = D_i - S\)
  • If \(x_i < 0\), the target is exceeded and achievement is impossible (-1).
  • Otherwise, perform \(x_i\) new operations and add \(x_i\) to the cumulative count \(S\).
• When \(i > N - K + 1\) (new operations cannot be started)
  • Since no new operation can begin at this section, the current cumulative increase \(S\) must exactly equal \(D_i\).
  • If \(D_i - S \neq 0\), achievement is impossible (-1).

Here, if we naively simulate adding values to \(K\) sections each time, each operation takes \(O(K)\), resulting in an overall complexity of \(O(NK)\). Since \(N \leq 3 \times 10^5\), this would exceed the time limit (TLE).

Instead, we manage \(S\) using a sliding window approach. When advancing to section \(i\), we subtract the operation that has fallen out of the influence range (namely, the operation \(x_{i-K}\) starting at section \(i-K\)) from \(S\) (\(S \leftarrow S - x_{i-K}\)), allowing us to update the current cumulative influence \(S\) in \(O(1)\).

---

Algorithm

1. For each section \(i\), compute the required increase \(D_i = B_i - A_i\). If any \(D_i < 0\) at this point, output -1 and terminate.
2. Prepare an array \(x\) (size \(N+1\), initialized to \(0\)) to record operation counts, a current cumulative operation count \(S = 0\), and a total answer ans = 0.
3. Loop from \(i = 1\) to \(N\) (using 1-indexed notation):
   • Step A: If \(i - K \geq 1\), subtract the operation count that has fallen out of the influence range: \(S \leftarrow S - x_{i-K}\)
   • Step B:
     • If \(i \leq N - K + 1\):

          * Compute the required additional operations $x_i = D_{i} - S$.
          * If $x_i < 0$, the target is exceeded, so output `-1` and terminate.
          * Update $S \leftarrow S + x_i$ and add $x_i$ to `ans`.
       

     • If \(i > N - K + 1\):

          * No new operations can be performed, so check whether the current $S$ equals $D_i$.
          * If $D_i - S \neq 0$, it does not match the target, so output `-1` and terminate.
       

4. If the loop completes without contradiction, output ans.

---

Complexity

• Time Complexity: \(O(N)\) For each section \(i\), we only perform a constant number of comparisons and additions/subtractions, so the overall complexity is \(O(N)\), which is well within the time limit.
• Space Complexity: \(O(N)\) We use \(O(N)\) memory to store the input arrays, the difference array \(D\), and the operation count array \(x\).

---

Implementation Notes

• Overflow Considerations: The maximum required number of operations can reach up to \(3 \times 10^{14}\). In Python, arbitrary-precision integers are handled automatically, so this is not an issue. However, when implementing in other languages such as C++ or Java, you need to use 64-bit integer types (such as long long in C++) for variables holding operation counts and their sums.

• Index Correspondence: In the code, section indices are 0-indexed (from \(0\) to \(N-1\)), while the operation management array \(x\) is handled as 1-indexed (from \(1\) to \(N\)). This makes it easier to prevent out-of-bounds access and results in cleaner implementation.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2 : 2 + N]]
    B = [int(x) for x in data[2 + N : 2 + 2 * N]]

    D = [0] * N
    for i in range(N):
        D[i] = B[i] - A[i]
        if D[i] < 0:
            print(-1)
            return

    x = [0] * (N + 1)
    S = 0
    ans = 0

    limit = N - K + 1
    for i in range(1, N + 1):
        if i - K >= 1:
            S -= x[i - K]

        if i <= limit:
            xi = D[i - 1] - S
            if xi < 0:
                print(-1)
                return
            x[i] = xi
            S += xi
            ans += xi
        else:
            if D[i - 1] - S != 0:
                print(-1)
                return

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.