Overview

This problem asks us to find the maximum sum among all contiguous subsequences of length \(K\) from a sequence that include the specified position \(D\).

Analysis

The starting position \(l\) of a valid interval must include the \(D\)-th section, so the possible range of \(l\) is restricted. Specifically, \(l\) is limited to the range \([D-K+1, D]\) (within the bounds of the sequence) so that \(D\) falls within the interval. The size of this range is at most around \(K\), and \(K\) can be as large as \(N\). However, since \(N\) can be up to \(10^6\), directly computing the sum for all possible \(l\) values is still fast enough.

Algorithm

1. Read the input (\(N\), \(K\), \(D\), sequence \(A\))
2. Convert \(D\) to 0-indexed (\(D_{index} = D-1\))
3. Compute the range of valid starting positions \(l\):
   • Left bound: \(\max(0, D_{index} - K + 1)\)
   • Right bound: \(\min(N-K, D_{index}) + 1\) (the range is half-open, i.e., left-closed right-open)
4. Build a prefix sum array \(\text{prefix}\) (\(\text{prefix}[i] = A_0 + A_1 + \cdots + A_{i-1}\))
5. For all possible \(l\), compute the sum of the interval \([l, l+K-1]\) using the prefix sum and find the maximum value

Complexity

• Time complexity: \(O(N)\)
  • \(O(N)\) for building the prefix sum
  • \(O(K)\) for scanning the intervals (at most \(O(N)\))
• Space complexity: \(O(N)\)
  • For the prefix sum array

Implementation Notes

• By using prefix sums, the sum of each interval can be computed in \(O(1)\)

• It is important to accurately compute the range of \(l\) (pay attention to boundary conditions)

• The initial value for the maximum should be set to a very small value (\(-10^{18}\)) (since negative values may end up being the maximum)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    D_index = D - 1
    
    left_bound = max(0, D_index - K + 1)
    right_bound = min(N - K, D_index) + 1
    
    max_sum = -10**18
    prefix = [0] * (N + 1)
    for i in range(1, N + 1):
        prefix[i] = prefix[i-1] + A[i-1]
    
    for l in range(left_bound, right_bound):
        r = l + K - 1
        current_sum = prefix[r+1] - prefix[l]
        if current_sum > max_sum:
            max_sum = current_sum
            
    print(max_sum)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.