Overview

Given an integer sequence \(A\) of length \(N\), select a contiguous subsequence (interval) of length \(W\), and find the maximum value of “the sum of the interval” plus “the minimum value in the interval \(\times K\)”.

Analysis

The key to this problem is how to efficiently compute “the interval sum” and “the interval minimum” for all intervals (there are \(N-W+1\) in total).

1. Naive Approach

For each interval starting at position \(l\), if we sum up \(W\) elements and search for the minimum each time, it takes \(O(W)\) time per interval. The overall complexity becomes \(O(N \times W)\), which will not fit within the time limit given the constraint \(N=5 \times 10^5\).

2. Efficient Interval Sum (Sliding Window)

When sliding the interval one position to the right, the change in sum can be computed by simply “adding the new element entering the window and subtracting the element leaving the window.” This allows us to update the interval sum in \(O(1)\) per step.

3. Efficient Interval Minimum (Sliding Window Minimum)

An algorithm called “Sliding Window Minimum (Monotonic Queue)” efficiently computes the minimum of an interval. Using a deque (double-ended queue), we manage elements while maintaining the following conditions: - The deque stores indices such that their corresponding values are in ascending order. - When adding a new element \(A_i\), all elements at the back of the deque that are greater than or equal to \(A_i\) are removed, since they “can never be the minimum in the future.” - Indices that have gone out of range (fallen off the left end) are removed from the front.

Using this technique, the front of the deque always points to the index of the minimum value in the current interval, and the minimum can be obtained in amortized \(O(1)\) per step.

Algorithm

1. For the first interval of length \(W\), compute the sum and build the deque using the sliding window minimum algorithm.
2. Compute the evaluation value \(\text{sum} + K \times \min\) for the first interval, and set it as the tentative maximum.
3. Slide the interval one position to the right at a time, repeating the following operations:
   • Update the interval sum: current_sum += A[i] - A[i-W]
   • If the front of the deque is out of range (i-W), remove it.
   • Remove elements from the back of the deque that are greater than A[i], then add i.
   • Compute current_sum + K * A[dq[0]] and update the maximum.
4. Output the final maximum.

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to the deque at most once and removed at most once. The overall loop runs \(N\) times, so the algorithm runs in linear time.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for storing the sequence \(A\) and managing the deque.

Implementation Notes

• Fast I/O: Since \(N\) is large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• Sign of K: This algorithm works correctly even when \(K\) is negative. If \(K\) is negative, a “smaller minimum (larger in the negative direction)” may lead to a larger evaluation value, but since the sliding window minimum always returns the exact minimum, we can simply plug it into the formula without any issues.

  Source Code

import sys
from collections import deque

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    # 大量のデータを扱うため、sys.stdin.read().split() が高速です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 数列の長さ, W: 区間の長さ, K: 最小値に掛ける係数
    n = int(input_data[0])
    w = int(input_data[1])
    k = int(input_data[2])
    
    # 数列 A を整数のリストとして読み込みます
    a = list(map(int, input_data[3:]))
    
    # スライディングウィンドウを用いて各区間の総和と最小値を効率的に求めます
    # dq は現在のウィンドウ内の最小値の候補となる要素のインデックスを保持するデックです
    dq = deque()
    
    # 最初のウィンドウ（インデックス 0 から W-1）の処理
    current_sum = sum(a[:w])
    for i in range(w):
        val = a[i]
        # デック内の要素のうち、現在の要素以上のものは最小値になり得ないため取り除きます
        while dq and a[dq[-1]] >= val:
            dq.pop()
        dq.append(i)
    
    # 最初の区間の評価値を計算し、最大値の初期値とします
    # 評価値 = 区間の総和 + K * 区間の最小値
    max_eval = current_sum + k * a[dq[0]]
    
    # ウィンドウを 1 つずつ右にずらしながら評価値を計算します
    # i は新しくウィンドウに入る要素のインデックスです
    for i in range(w, n):
        # ウィンドウの総和を更新：新しい要素を加え、範囲外になった要素を引きます
        val = a[i]
        current_sum += val - a[i - w]
        
        # デックの先頭がウィンドウの範囲外（インデックス i-w）になった場合は取り除きます
        if dq[0] == i - w:
            dq.popleft()
        
        # デックを維持：現在の要素 val 以上の要素を末尾から取り除き、現在のインデックスを追加します
        while dq and a[dq[-1]] >= val:
            dq.pop()
        dq.append(i)
        
        # 現在のウィンドウの評価値を計算し、最大値を更新します
        # a[dq[0]] は常に現在のウィンドウ内での最小値となります
        current_eval = current_sum + k * a[dq[0]]
        if current_eval > max_eval:
            max_eval = current_eval
            
    # 結果を出力します
    sys.stdout.write(str(max_eval) + '\n')

if __name__ == '__main__':
    solve()

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