Overview

Given a sequence of length \(N\), select \(W\) consecutive elements and maximize the evaluation value defined as “sum of the interval \(+\) \(K\) \(\times\) minimum of the interval.” This can be solved in \(O(N)\) using a sliding window minimum (monotone deque).

Analysis

Structure of the Evaluation Value

The evaluation value of the interval \([l, l+W-1]\) is expressed by the following formula:

\[\text{evaluation value} = \sum_{i=l}^{l+W-1} A_i + K \times \min(A_l, \ldots, A_{l+W-1})\]

We need to compute this value for all window positions \(l\) and find the maximum.

Issues with the Naive Approach

If we naively compute the sum and minimum for each window, it takes \(O(W)\) per window, and there are \(N - W + 1\) windows, resulting in \(O(NW)\) overall. When \(N\) is up to \(5 \times 10^5\), this won’t be fast enough if \(W\) is large.

Ideas for Optimization

• Interval sum: By precomputing a prefix sum, we can obtain the sum of each window in \(O(1)\).
• Interval minimum: By managing a sliding window minimum with a monotone deque, we can obtain the minimum of each window in amortized \(O(1)\).

This allows us to process everything in \(O(N)\).

Algorithm

1. Precomputing the Prefix Sum

Define:

\(\text{prefix}[0] = 0, \quad \text{prefix}[i] = A_1 + A_2 + \cdots + A_i\)

Then the sum of the interval \([l, l+W-1]\) (0-indexed) can be obtained in \(O(1)\) as \(\text{prefix}[l+W] - \text{prefix}[l]\).

2. Sliding Window Minimum with a Monotone Deque

Store indices in a deque (double-ended queue) and maintain them so that the corresponding values of \(A\) are monotonically increasing.

While scanning the array from left to right, perform the following operations:

1. Removal from the back: If the new element \(A[i]\) is less than or equal to the element at the back of the deque, remove the back (since the new element is smaller, the old element will never be the minimum in the future).
2. Insertion: Add \(i\) to the back of the deque.
3. Removal from the front: If the index at the front of the deque is outside the window \([i-W+1, i]\), remove it.
4. Retrieving the minimum: The front of the deque is the index of the minimum value in the current window.

3. Computing the Evaluation Value and Updating the Maximum

When the window is complete at \(i \geq W - 1\):

\[\text{score} = (\text{prefix}[i+1] - \text{prefix}[i-W+1]) + K \times A[\text{deque front}]\]

Compute this and update the answer.

Concrete Example

For \(A = [3, 1, 4, 1, 5],\ W = 3,\ K = 2\):

\(l\) (0-indexed)	Interval	Sum	Minimum	Evaluation Value
0	\([3,1,4]\)	\(8\)	\(1\)	\(8 + 2 \times 1 = 10\)
1	\([1,4,1]\)	\(6\)	\(1\)	\(6 + 2 \times 1 = 8\)
2	\([4,1,5]\)	\(10\)	\(1\)	\(10 + 2 \times 1 = 12\)

The maximum is \(12\).

Complexity

• Time complexity: \(O(N)\) (building the prefix sum takes \(O(N)\), and the deque operations are amortized \(O(N)\) since each element is added and removed at most once)
• Space complexity: \(O(N)\) (for the prefix sum array and the deque)

Implementation Notes

• Store indices in the deque and compare values using \(A[\text{index}]\). This also makes it easy to check whether an index is outside the window range by simple index comparison.

• When \(K\) is negative, a smaller minimum makes \(K \times \min\) larger (negative × negative = positive), so windows with smaller minimums may be advantageous. However, since this code accurately computes the minimum for each window and calculates the evaluation value, it works correctly regardless of the sign of \(K\).

• The answer can be very large (up to approximately \(5 \times 10^{14}\)), so 64-bit integers are necessary. In Python, however, there is no need to worry about integer overflow.

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    W = int(input_data[1])
    K = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # Precompute prefix sums
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # For each window starting at l (0-indexed), the score is:
    # sum(A[l..l+W-1]) + K * min(A[l..l+W-1])
    # = (prefix[l+W] - prefix[l]) + K * min(A[l..l+W-1])
    
    # We need to efficiently compute the minimum of each window of size W.
    # But since K can be negative, we might want the maximum instead.
    # Actually, we want to maximize: sum + K * min
    # If K >= 0, larger min is better (for fixed sum), so we want large min.
    # If K < 0, smaller min is worse (makes K*min more negative), so we want large min too? No...
    # Actually it's not that simple because different windows have different sums AND different mins.
    
    # Approach: For each possible value of the minimum, consider all windows where that element
    # is the minimum. This is a classic approach using a monotone stack.
    
    # Alternative approach: iterate over all windows using a sliding window minimum (deque).
    # This is O(N) and straightforward.
    
    # Sliding window min using deque
    dq = deque()  # stores indices, maintaining A[indices] in increasing order
    
    ans = -float('inf')
    
    for i in range(N):
        # Remove elements from back that are >= A[i] (we maintain increasing order for min)
        while dq and A[dq[-1]] >= A[i]:
            dq.pop()
        dq.append(i)
        
        # Remove elements that are out of the window
        # Window is [i - W + 1, i]
        while dq[0] < i - W + 1:
            dq.popleft()
        
        # If we have a full window
        if i >= W - 1:
            l = i - W + 1
            window_sum = prefix[i + 1] - prefix[l]
            window_min = A[dq[0]]
            score = window_sum + K * window_min
            if score > ans:
                ans = score
    
    print(ans)

main()

---

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