Overview

This problem asks you to determine whether you can transform an array \(A\) of length \(N\) into an array \(B\) by repeatedly performing an operation that adds \(1\) to \(K\) consecutive elements, and if possible, find the minimum number of operations.

Analysis

1. Focus on the Differences

First, for each section \(i\), calculate how much more moisture needs to be added. If we define \(D_i = B_i - A_i\), the goal is to make all \(D_i\) equal to \(0\). Since the operation can only “increase” moisture, if even one section has \(D_i < 0\), it is impossible to achieve the goal (-1).

2. Greedy Approach: Deciding from Left to Right

The key insight of this problem is “determining the moisture level sequentially starting from the leftmost section.”

To bring section \(1\) to its target value, the only option is to perform a range addition of length \(K\) starting at section \(1\). This is because no starting position to the left of section \(1\) (negative index) can be chosen for an operation that includes section \(1\). Therefore, it is determined that we must perform exactly \(D_1\) operations starting at section \(1\).

Similarly, once section \(1\) is adjusted, we focus on section \(2\). After accounting for operations already applied to section \(2\) (those starting at section \(1\)), if there is still a deficit, we must compensate with operations starting at section \(2\). By repeating this for \(i = 1, 2, \ldots, N-K+1\), the number of operations required at each position is uniquely determined.

3. Optimization (Application of the Imos Method)

If we naively “add \(1\) to each element in the range,” each operation costs \(O(K)\), and in the worst case the total time complexity becomes \(O(NK)\). Since \(N, K \leq 2 \times 10^5\), this would not meet the time limit.

Therefore, we need to efficiently manage “the total number of operations currently affecting a given position.” This can be solved using the idea of the “imos method” or “difference array.” - A variable current_ops maintains the total number of operations currently affecting the current section. - An array diff is prepared, where diff[i] records “the number of operations that end at section \(i\).” - When moving to the next section, by adding diff[i] to current_ops (subtracting the ending operations), we can always know the current state in \(O(1)\).

Algorithm

1. Calculate the deficit for each section: \(D_i = B_i - A_i\). If any \(D_i < 0\), output -1.
2. Initialize current_ops (number of currently active operations) and total_ops (total number of operations), and prepare an array diff to manage when operations end.
3. Scan from \(i = 0\) to \(N-1\):
   • Add diff[i] to current_ops (reflect the effect of operations ending at this position).
   • If \(i \leq N-K\) (still within the range where operations can start):
     • Calculate the additional operations needed: needed = D[i] - current_ops.
     • If needed < 0, the target has already been exceeded, so it is impossible (-1).
     • If needed > 0, add needed to both total_ops and current_ops, and schedule a subtraction of needed at diff[i+K].
   • If \(i > N-K\) (no longer within the range where operations can start):
     • If D[i] does not equal current_ops, adjustment is impossible, so output -1.
4. If the scan completes without contradictions, output total_ops.

Complexity

• Time Complexity: \(O(N)\)
  • The array is scanned a constant number of times, and processing for each element takes constant time.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the deficit array \(D\) and the operation-ending management array diff.

Implementation Notes

• Operation end position: An operation of length \(K\) starting at section \(i\) affects up to section \(i + K - 1\). Therefore, its influence ceases at section \(i + K\). When recording a negative value at diff[i + K], care must be taken to ensure the index does not exceed \(N\).

• Large numbers: \(A_i\), \(B_i\), and the number of operations can become very large values. Use a language that handles large integers natively (like Python), or in other languages, use 64-bit integer types (long long, etc.).

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してメモリ効率よくデータを取得します
    it = iter(input_data)
    
    try:
        N = int(next(it))
        K = int(next(it))
        
        # A_i: 各区画の現在の水分量
        A = [int(next(it)) for _ in range(N)]
        # B_i: 各区画の目標の水分量
        B = [int(next(it)) for _ in range(N)]
    except StopIteration:
        return
    
    # 各区画で不足している水分量 D_i を計算します
    D = [B[i] - A[i] for i in range(N)]
    
    # 水分量を減らす操作はできないため、目標値が現在値より小さい場合は不可能です
    for d in D:
        if d < 0:
            print("-1")
            return
            
    # いもす法（差分配列）の考え方を用いて、範囲加算を効率的に管理します
    # diff[i] は、地点 i で新しく終了する操作による影響（減少分）を記録します
    diff = [0] * (N + 1)
    current_ops = 0 # 現在の区画 i に影響を与えている操作の合計回数
    total_ops = 0   # これまでに行った操作の総回数
    
    # 左から順に、各区画の水分量を目標値に合わせるように貪欲に操作を決定します
    # 操作の開始位置として選べるのは 0 から N-K までです
    for i in range(N - K + 1):
        # 以前の操作のうち、この区画で終了するものの影響を反映します
        current_ops += diff[i]
        
        # 現在の区画 i で不足している水分量
        needed = D[i] - current_ops
        
        if needed < 0:
            # すでに目標値を超えてしまっている場合は不可能です
            print("-1")
            return
        
        if needed > 0:
            # 不足分を補うため、区画 i を開始点とする操作を needed 回行います
            total_ops += needed
            current_ops += needed
            # この操作は区画 i + K - 1 で終わるため、i + K で影響を差し引きます
            if i + K <= N:
                diff[i + K] -= needed
            
    # 操作を開始できない残りの区画（N-K+1 から N-1）について、
    # すでに適用された操作だけで目標値に達しているか確認します
    for i in range(N - K + 1, N):
        current_ops += diff[i]
        if D[i] != current_ops:
            # 目標値に一致しない場合は、これ以上調整できないため不可能です
            print("-1")
            return
            
    # すべての区画が目標値に一致した場合、合計操作回数を出力します
    print(total_ops)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.