Overview

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

By using a “Greedy” approach that determines values from the left end in order, combined with a “Sliding Window” technique to efficiently manage the cumulative additions within an interval, we can solve this efficiently in \(O(N)\) time complexity.

Analysis

1. Focusing on the Differences

First, for each section \(i\), let the required increase be \(D_i = B_i - A_i\). Since operations cannot “decrease” the moisture level, if there exists even one section where \(D_i < 0\), it is impossible to achieve the goal. In that case, we output -1 and terminate. From here on, we assume \(D_i \ge 0\) for all \(i\).

2. Greedily Deciding from the Left End

An operation “adds \(1\) to the interval of length \(K\) starting at section \(l\).” Let’s focus on the leftmost section \(i = 0\) (0-indexed). The only operation that can cover section \(0\) is the operation with section \(0\) as its left end (\(l = 0\)). Therefore, to bring section \(0\) to its target value, we must perform the operation with section \(0\) as its left end exactly \(D_0\) times. Neither more nor fewer will work.

Performing this operation increases the moisture level of sections \(0\) through \(K-1\) all by \(D_0\).

Next, let’s focus on section \(1\). Section \(1\) has already had its moisture level increased by \(D_0\) from the previous operation. Therefore, the number of times we should perform the operation with section \(1\) as its left end is uniquely determined as the remaining required amount: \(D_1 - D_0\). If \(D_1 - D_0 < 0\), this means section \(1\)’s moisture level has already exceeded the target value, and since we cannot decrease it further, achievement is impossible (-1).

In this way, we can greedily determine, from left to right, “how many times to perform the operation with each section as its left end to make up the deficit at that section.”

3. Speeding Up the Operation Simulation

In general, when processing section \(i\), let \(S_i\) be the total value already added to section \(i\) by previously determined operations. If we let \(x_i\) be the number of operations with section \(i\) as the left end, it can be determined as follows:

• When \(i \le N - K\) (when an interval of length \(K\) can be secured to the right):
  • Determine \(x_i = D_i - S_i\).
  • If \(x_i < 0\), the target value has been exceeded, so achievement is impossible (-1).
• When \(i > N - K\) (when an interval of length \(K\) cannot be secured to the right):
  • No operation can start at this section (\(x_i = 0\)).
  • Therefore, the already added value \(S_i\) must exactly match the target difference \(D_i\) (\(D_i = S_i\)). If they don’t match, achievement is impossible (-1).

Here, if we naively compute \(S_i\) each time, we would need to sum the most recent \(K\) values of \(x\), resulting in \(O(NK)\) total time. However, the operations that affect section \(i\) are the \(K-1\) values from \(x_{i-K+1}\) to \(x_{i-1}\). Therefore, \(S_i\) can be expressed using the previous state \(S_{i-1}\) as: $\(S_i = S_{i-1} + x_{i-1} - x_{i-K}\)\( By using this sliding window approach, we can update each \)S_i\( in \)O(1)$ as we proceed.

Algorithm

1. For each \(i\), compute the required amount \(D_i = B_i - A_i\). If any \(D_i < 0\), output -1.
2. Prepare an array \(x\) (all initialized to \(0\)) to record the number of operations with each section as the left end, and a variable current_sum for the total additions applied to the current section.
3. For \(i = 0\) to \(N-1\), do the following:
   • Add \(x[i-1]\) to current_sum and subtract \(x[i-K]\) (which has gone out of range), to obtain the total additions applied to the current section \(i\) in \(O(1)\).
   • If \(i \le N - K\):
     • Set \(x[i] = D_i - \text{current\_sum}\).
     • If \(x[i] < 0\), output -1 and terminate.
     • Add \(x[i]\) to the total operation count total_ops.
   • If \(i > N - K\):
     • If \(D_i \neq \text{current\_sum}\), the target value cannot be matched, so output -1 and terminate.
4. If all sections are processed without contradiction, total_ops is the desired minimum number of operations.

Complexity

• Time Complexity: \(O(N)\) The processing for each section \(i\) involves only a constant number of additions and subtractions via the sliding window, so the entire algorithm runs in \(O(N)\) time.
• Space Complexity: \(O(N)\) \(O(N)\) memory is used to store the input arrays \(A, B\), the difference array \(D\), and the operation count array \(x\).

Implementation Notes

• Overflow Prevention: According to the constraints, the total number of operations can reach up to \(3 \times 10^{14}\). This exceeds the maximum value of a typical 32-bit integer type (such as int in C++, approximately \(2 \times 10^9\)), so be sure to use a 64-bit integer type (such as long long in C++) for calculations involving operation counts and moisture levels.

• Index Boundary Conditions: When updating current_sum, if \(i - 1 < 0\) or \(i - K < 0\), appropriate conditional branches (such as if (i >= 1) or if (i >= K)) must be used to prevent out-of-bounds array access.

  Source Code

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(N);
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }

    vector<long long> D(N);
    for (int i = 0; i < N; ++i) {
        D[i] = B[i] - A[i];
        if (D[i] < 0) {
            cout << -1 << "\n";
            return 0;
        }
    }

    vector<long long> x(N, 0);
    long long current_sum = 0;
    long long total_ops = 0;

    for (int i = 0; i < N; ++i) {
        if (i >= 1) {
            current_sum += x[i - 1];
        }
        if (i >= K) {
            current_sum -= x[i - K];
        }

        if (i <= N - K) {
            long long val = D[i] - current_sum;
            if (val < 0) {
                cout << -1 << "\n";
                return 0;
            }
            x[i] = val;
            total_ops += val;
        } else {
            if (D[i] != current_sum) {
                cout << -1 << "\n";
                return 0;
            }
        }
    }

    cout << total_ops << "\n";
    return 0;
}

---

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