Overview

For each contiguous subsequence of length \(W\), we compute “interval sum \(+\;K \times\) interval minimum” and find its maximum value. To efficiently process all intervals, we maintain the interval sum with sliding updates and manage the interval minimum with a monotonic queue (deque).

Analysis

For each \(l\), the evaluation value is $\(\left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l,\ldots,A_{l+W-1})\)\( In other words, for each window (sliding window) of length \)W$, if we know:

• The sum of the interval
• The minimum of the interval

then we can immediately compute the evaluation value (even if \(K\) is negative, the formula is the same, and the way we find the minimum itself does not change).

Why the naive solution is too slow

For every \(l\): - Summing \(W\) elements each time (\(O(W)\)) - Finding the minimum among \(W\) elements each time (\(O(W)\))

results in a total of \(O(NW)\), which is too slow for a maximum of \(5\times 10^5\).

How to solve it

• Interval sum can be updated in \(O(1)\) by “adding the new right element and removing the old left element.”
• Interval minimum can be computed in \(O(N)\) overall using a “monotonically increasing deque (monotonic queue),” since each element enters and leaves the deque at most once.

Example: \(A=[3,1,4,2],\;W=3\)
The windows are \([3,1,4]\) (minimum \(1\)), \([1,4,2]\) (minimum \(1\)).
Instead of searching for the minimum each time, we discard elements from the back of the deque that can never become the minimum (because they are too large), ensuring that the front of the deque always holds the minimum.

Algorithm

1. Process \(i=0..N-1\) from left to right.
2. Update interval sum \(s\):
   • \(s \leftarrow s + A[i]\)
   • If \(i \ge W\), subtract the element leaving the window: \(s \leftarrow s - A[i-W]\)
3. Update the deque dq (which stores indices) that manages the interval minimum:
   • Maintain the property that values \(A[dq]\) in the deque are monotonically increasing.
   • Before inserting the new element \(A[i]\), pop from the back while $\(A[dq[-1]] \ge A[i]\)$ (if the back is larger, it can never be the minimum in the future).
   • Then dq.append(i).
4. Remove the front of the deque if it has left the window:
   • The window is \([i-W+1,\,i]\) (when \(i \ge W-1\)), so if $\(dq[0] \le i-W\)$ then popleft().
5. If \(i \ge W-1\), the window is complete, so compute the evaluation value:
   • The minimum is \(A[dq[0]]\)
   • Evaluation value \(val = s + K \times A[dq[0]]\)
   • Update the maximum

This processes all windows exactly once.

Complexity

• Time complexity: \(O(N)\) (each element enters and leaves the deque at most once)
• Space complexity: \(O(W)\) (the deque holds at most about the window size number of elements)

Implementation Notes

• Storing indices rather than values in the deque makes it easy to check whether an element has left the window (by comparing with \(i-W\)).

• For updating the monotonic queue, performing the operations in this order is stable:

  • Pop from the back anything that is “larger (or equal)” (>=)
  • Pop from the front anything outside the window

• Even if \(K\) or \(A_i\) is negative, the processing is the same — just apply the evaluation formula as-is.

• In Python, since the input can be large, using sys.stdin.buffer.read() speeds up input processing.

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, W, K = data[0], data[1], data[2]
    A = data[3:3+N]

    dq = deque()  # indices, A[dq] increasing
    s = 0
    ans = None

    for i, x in enumerate(A):
        s += x
        if i >= W:
            s -= A[i - W]

        while dq and A[dq[-1]] >= x:
            dq.pop()
        dq.append(i)

        while dq[0] <= i - W:
            dq.popleft()

        if i >= W - 1:
            val = s + K * A[dq[0]]
            if ans is None or val > ans:
                ans = val

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.