Overview

Given an integer sequence of length \(N\), select a contiguous interval of \(W\) elements. The problem asks to find the maximum evaluation value, which is the sum of elements in the interval plus the product of the minimum value in the interval and \(K\).

Analysis

In a naive approach, for all possible intervals (\(N - W + 1\) intervals), computing the minimum value within each interval every time takes \(O(W)\), resulting in an overall time complexity of \(O(NW)\). Since \(N\) and \(W\) can be up to \(5 \times 10^5\) in this problem, this approach cannot finish within the time limit.

Therefore, we need to efficiently compute the minimum value within the interval. To quickly find the minimum value in a sliding window, the sliding window minimum algorithm using a double-ended queue (deque) is effective. Using this algorithm, we can obtain the minimum value for each interval in \(O(1)\).

Algorithm

1. Prefix Sum Precomputation: To quickly compute the sum of each interval, create a prefix sum array prefix of length \(N+1\). It satisfies prefix[i] = A[0] + A[1] + ... + A[i-1].
2. Sliding Window Minimum Computation: Use a double-ended queue (deque) to maintain the indices of the minimum values within the current window. The queue is operated as follows:
   • Remove indices that have fallen outside the window (from the front)
   • If the new element is less than or equal to the element at the back of the queue, remove the back (to prepare for when a smaller value arrives)
   • Add the current index to the queue
3. Evaluation Value Computation: For each window position, compute the sum from the prefix sum array, use the value at the index at the front of the queue as the minimum value, and calculate the evaluation value. Scan through all windows while updating the maximum value.

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to the queue at most once and removed at most once
• Space complexity: \(O(N)\)
  • \(O(N)\) space is needed for the prefix sum array and the queue

Implementation Notes

• The prefix sum array sets index \(0\) to \(0\) and stores the sum up to the \(i\)-th element in prefix[i+1], so the sum of interval \([l, r]\) can be easily computed as prefix[r+1] - prefix[l].

• The queue stores indices, and actual values are referenced from array A.

• The starting position l of the window is computed as i - W + 1, and the evaluation value computation begins when i is at least \(W-1\).

• The initial value of max_val is set to a very small value (\(-10^{18}\)) to correctly handle negative evaluation values.

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0]); W = int(data[1]); K = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    if W == 0:
        print(0)
        return
        
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    dq = deque()
    max_val = -10**18
    
    for i in range(N):
        while dq and dq[0] < i - W + 1:
            dq.popleft()
            
        while dq and A[dq[-1]] >= A[i]:
            dq.pop()
            
        dq.append(i)
        
        if i >= W - 1:
            l = i - W + 1
            total = prefix[i + 1] - prefix[l]
            min_val = A[dq[0]]
            value = total + K * min_val
            if value > max_val:
                max_val = value
                
    print(max_val)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.