Overview

Given a sequence of length \(N\), find a contiguous subsequence of \(K\) elements that must include the \(D\)-th element and has the maximum sum.

Analysis

In this problem, if we naively enumerate all intervals and compute their sums by brute force, the worst-case time complexity would be \(O(N \cdot K)\), which is too slow given the constraint \(N \leq 10^6\).

The key insight is to enable fast computation of “interval sums.” This can be achieved using prefix sums.

Next, regarding which interval to choose, the starting position \(l\) of the interval must satisfy the following conditions: - \(1 \leq l \leq N - K + 1\) (the interval does not extend beyond the array) - \(l \leq D \leq l + K - 1\) (the interval contains the \(D\)-th element)

Rearranging these, we get: $\( D - K + 1 \leq l \leq D \)\( (1-indexed). Converting to 0-indexed: \)\( \max(0, D - K + 1) \leq l \leq \min(D, N - K) \)$

Within this range, we compute the interval sum \(A_l + A_{l+1} + \cdots + A_{l+K-1}\) for each \(l\) in \(O(1)\) using prefix sums, and find the maximum value.

Algorithm

1. Read the input and convert \(D\) to 0-indexed.
2. Compute the valid range for the starting position \(l\).
3. Build the prefix sum array.
4. For each \(l\) within the valid range, compute the interval sum from the prefix sums and update the maximum value.
5. Output the maximum value.

How to Use Prefix Sums

Define the prefix sum array \(acc\) of the sequence \(A\) as follows: $\( acc[i] = A[0] + A[1] + \cdots + A[i-1] \)\( With this, the sum of the interval \)[l, r]\( can be computed as \)acc[r+1] - acc[l]$.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Don’t forget to convert \(D\) to 0-indexed.

• Adding a 0 at the beginning of the prefix sum array simplifies the interval sum computation.

• Verify that the range of starting positions is non-empty (in this problem, the constraints guarantee this).

  Source Code

import sys
from itertools import accumulate

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

    # 1-indexed -> 0-indexed
    D -= 1

    # 区間の開始位置 l の範囲を計算
    # l <= D <= l + K - 1 => l >= D - K + 1 and l <= D
    # また、1 <= l <= N - K + 1 (0-indexedでは 0 <= l <= N - K)
    min_l = max(0, D - K + 1)
    max_l = min(D, N - K)

    if min_l > max_l:
        # 実際には制約により存在することが保証されているのでこのケースはないが念のため
        print(-float('inf'))
        return

    # 累積和を計算
    acc = [0] + list(accumulate(A))

    max_sum = -float('inf')
    for l in range(min_l, max_l + 1):
        current_sum = acc[l + K] - acc[l]
        if current_sum > max_sum:
            max_sum = current_sum

    print(max_sum)

if __name__ == "__main__":
    main()

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