Overview

This is a problem where you must select a contiguous interval of \(K\) sections that necessarily includes the favorite section \(D\), and maximize the total beauty. Using prefix sums, we can efficiently compute the sum of each interval and find the maximum among all valid intervals.

Analysis

Identifying the range of valid starting positions \(l\)

The interval consists of \(K\) sections from the \(l\)-th to the \((l+K-1)\)-th. The conditions that \(l\) must satisfy are the following three:

1. \(l \geq 1\) (does not extend beyond the left end)
2. \(l + K - 1 \leq N\), i.e., \(l \leq N - K + 1\) (does not extend beyond the right end)
3. \(l \leq D \leq l + K - 1\), i.e., \(l \leq D\) and \(l \geq D - K + 1\) (includes section \(D\))

Combining these:

\[l_{\min} = \max(1, \, D - K + 1)\]

\[l_{\max} = \min(N - K + 1, \, D)\]

Concrete example: For \(N = 7, K = 3, D = 4\): - \(l_{\min} = \max(1, 4 - 3 + 1) = \max(1, 2) = 2\) - \(l_{\max} = \min(7 - 3 + 1, 4) = \min(5, 4) = 4\) - Therefore \(l \in \{2, 3, 4\}\), meaning the candidate intervals are \([2,4], [3,5], [4,6]\). All of them include section \(4\).

Issues with the naive approach

If we sum \(K\) elements for each \(l\), computing one sum takes \(O(K)\), and since there are at most \(K\) candidates, the total complexity becomes \(O(K^2)\), which is too slow when \(K\) is large.

Speeding up with prefix sums

By precomputing prefix sums, we can compute the sum of any interval in \(O(1)\).

\[\text{prefix}[i] = A_1 + A_2 + \cdots + A_i, \quad \text{prefix}[0] = 0\]

Then, the sum of the interval \([l, l+K-1]\) is:

\[A_l + A_{l+1} + \cdots + A_{l+K-1} = \text{prefix}[l+K-1] - \text{prefix}[l-1]\]

Algorithm

1. Compute the prefix sum array \(\text{prefix}\) of array \(A\) in \(O(N)\).
2. Determine the valid range \([l_{\min}, l_{\max}]\) for \(l\).
3. For each \(l\) from \(l_{\min}\) to \(l_{\max}\), compute \(\text{prefix}[l+K-1] - \text{prefix}[l-1]\) and output the maximum value.

Complexity

• Time complexity: \(O(N)\)
  • \(O(N)\) for computing the prefix sums, \(O(l_{\max} - l_{\min} + 1) \leq O(K) \leq O(N)\) for searching over valid \(l\)
• Space complexity: \(O(N)\)
  • Size of the prefix sum array

Implementation Notes

• It is crucial to derive the range of \(l\) correctly. If even one condition is wrong, you may select an interval that does not include section \(D\), or an interval that extends beyond the promenade.

• Constructing the prefix sum array as 0-indexed with prefix[0] = 0, where prefix[i] represents the sum from \(A_1\) to \(A_i\), makes the interval sum computation straightforward.

• Since beauty values can be negative, the initial value for the maximum must be set to -float('inf').

• Since \(N\) can be as large as \(10^6\), using sys.stdin.read() to read all input at once ensures fast execution even in Python.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    D = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # l must satisfy:
    # 1 <= l, l + K - 1 <= N, l <= D <= l + K - 1
    # => l >= 1, l <= N - K + 1, l <= D, l >= D - K + 1
    l_min = max(1, D - K + 1)
    l_max = min(N - K + 1, D)
    
    best = -float('inf')
    # sum of A[l..l+K-1] = prefix[l+K-1] - prefix[l-1]
    # We can just iterate, but with prefix sums it's O(1) per query
    # Number of valid l values can be up to K which can be up to 2*10^5, so iteration is fine
    for l in range(l_min, l_max + 1):
        s = prefix[l + K - 1] - prefix[l - 1]
        if s > best:
            best = s
    
    print(best)

main()

---

This editorial was generated by claude4.6opus-thinking.