Overview

Given a sequence of length \(N\), select a contiguous subsequence of length \(W\) and maximize the evaluation value defined as “sum + minimum value × \(K\)”.

Analysis

In this problem, we compute the evaluation value for all contiguous subsequences of length \(W\) and find the maximum.

The evaluation value is defined as follows: $\( \text{Evaluation Value} = \left(\sum_{i=l}^{l+W-1} A_i\right) + K \times \min(A_l, A_{l+1}, \ldots, A_{l+W-1}) \)$

A naive approach that computes the sum and minimum for each interval every time would have a time complexity of \(O(NW)\), which is too slow given the constraints \(N, W \leq 5 \times 10^5\).

Therefore, the following optimizations are needed:

• Interval sum: Compute in \(O(1)\) using prefix sums.
• Interval minimum: To efficiently find the minimum in a sliding window, use a deque (double-ended queue).

By doing this, we can process everything efficiently.

Algorithm

1. Prefix Sum Preprocessing

   • Create a prefix sum array where prefix[i] := \(A_1 + A_2 + \cdots + A_{i-1}\).
   • The sum of interval \([l, r]\) can be obtained in \(O(1)\) as prefix[r+1] - prefix[l].

2. Minimum Value Management with Sliding Window

   • Move a window of length \(W\) from left to right, efficiently retrieving the minimum value within it.
   • Manage using a deque with the following rules:
     • If the element corresponding to the index at the back of the deque is greater than or equal to the current element, remove it (it is unnecessary as a minimum candidate)
     • If the index at the front of the deque is outside the current window, remove it
     • The front of the deque always holds the index of the minimum value in the current window

3. Evaluation Value Computation and Update

   • For each interval \([l, l+W-1]\), use the above to find the sum and minimum, and compute the evaluation value.
   • Maintain the maximum evaluation value and output it at the end.

Complexity

• Time complexity: \(O(N)\)
  Each element is added to and removed from the deque at most once, so the overall processing is linear.
• Space complexity: \(O(N)\)
  Required for the prefix sum table and the deque.

Implementation Notes

• Store indices in the deque, and use A[index] to access actual values.

• Compute the evaluation value when the window reaches exactly length \(W\) (i.e., when r >= W - 1).

• Use prefix sums to efficiently compute interval sums.

  Source Code

from collections import deque
import sys

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

    # 累積和を計算
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]

    # 双方向キューを使って、区間 [l, l+W-1] の最小値を効率的に管理
    dq = deque()
    max_value = float('-inf')

    for r in range(N):
        # 現在の値より大きい要素を deque から削除
        while dq and A[dq[-1]] >= A[r]:
            dq.pop()
        dq.append(r)

        # 区間 [l, r] が W より長い場合は左端を削除
        if dq[0] <= r - W:
            dq.popleft()

        # 区間が W になったら評価値を計算
        if r >= W - 1:
            l = r - W + 1
            current_sum = prefix[r + 1] - prefix[l]
            min_val = A[dq[0]]
            value = current_sum + K * min_val
            if value > max_value:
                max_value = value

    print(max_value)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.