Overview

Among all contiguous intervals of exactly length \(K\), we restrict ourselves to those that must include block \(D\), and find the maximum total beauty.

Analysis

Key Observation 1: The range of possible starting positions \(l\) is narrow

An interval of length \(K\) is \([l,\, l+K-1]\). The condition for it to include block \(D\) is $\( l \le D \le l+K-1 \)\( Solving for \)l\(: \)\( D-K+1 \le l \le D \)\( Additionally, the condition that the interval does not go out of bounds: \)\( 1 \le l \le N-K+1 \)\( Combining these, we only need to check \)l\( in the range: \)\( L=\max(1,\, D-K+1),\quad R=\min(D,\, N-K+1) \)$

(Example) When \(N=10, K=4, D=6\):
\(D-K+1=3\), so \(l \in [3,6]\). Indeed, only intervals starting at positions 3, 4, 5, 6 contain block 6.

Why a naive approach doesn’t work

If we sum \(K\) elements for each \(l\), we perform up to \((N-K+1)\) iterations each adding \(K\) values: $\( O(NK) \)\( For \)N=10^6$, this is far too slow.

Solution: Sliding Window (Two-pointer technique)

Each time we “shift the window one position to the right” for an interval of length \(K\): - Add the newly entering element - Subtract the element that falls out

This allows us to update in \(O(1)\) per position, resulting in \(O(N)\) overall.

Algorithm

1. Compute the range of valid starting positions \([L,R]\): $\(L=\max(1, D-K+1),\ R=\min(D, N-K+1)\)$
2. Read the array from left to right while maintaining the “current interval sum” \(window\_sum\) for a window of length \(K\).
   • Sum the first \(K\) elements to create the initial interval sum (starting position \(l=1\)).
   • For each subsequent step, “add the entering value and subtract the leaving value.”
3. Compute the starting position \(l\) at each step, and update the maximum only when \(L \le l \le R\).
4. Output the maximum value.

In this code, to quickly subtract the leaving value, we store the most recent \(K\) elements in a ring buffer (an array of size \(K\) that is reused cyclically). This allows processing without storing all elements \(A_1..A_N\).

Complexity

• Time complexity: \(O(N)\) (each element is processed with a constant number of operations)
• Space complexity: \(O(K)\) (only the most recent \(K\) elements are stored as a ring buffer)

Implementation Notes

• Computing the range of starting positions \([L,R]\) is the core of the problem. Getting this wrong will either mix in intervals that don’t contain \(D\) or miss valid candidates, leading to WA.

• The answer can be negative, so initializing it to \(0\) can cause errors. In the code, we use ans=None and initialize with the first interval that satisfies the condition.

• Since \(N \le 10^6\), fast input is important in Python. We use sys.stdin.buffer.read() with a custom parser for speedup.

• The interval sum can be as large as \(K \cdot 10^9\), so it must be handled with 64-bit integers (Python has arbitrary precision, but the buffer uses array('q')).

  Source Code

import sys
from array import array

data = sys.stdin.buffer.read()
n_data = len(data)
p = 0

def next_int():
    global p
    while p < n_data and data[p] <= 32:
        p += 1
    sign = 1
    if data[p] == 45:  # b'-'
        sign = -1
        p += 1
    num = 0
    while p < n_data:
        c = data[p]
        if c <= 32:
            break
        num = num * 10 + (c - 48)
        p += 1
    return sign * num

N = next_int()
K = next_int()
D = next_int()

L = max(1, D - K + 1)
R = min(D, N - K + 1)

buf = array('q', [0]) * K
window_sum = 0
ans = None

for i in range(1, N + 1):
    x = next_int()
    if i <= K:
        window_sum += x
        buf[i - 1] = x
        if i == K:
            l = 1
            if L <= l <= R:
                ans = window_sum
    else:
        pos = (i - 1) % K
        old = buf[pos]
        buf[pos] = x
        window_sum += x - old
        l = i - K + 1
        if L <= l <= R:
            if ans is None or window_sum > ans:
                ans = window_sum

print(ans)

---

This editorial was generated by gpt-5.2-high.