Overview

This problem asks us to choose an interval \([s, s+D)\) of length \(D\) for \(N\) flower beds lined up on a number line in a way that maximizes the number of flowers within that interval. The final answer will be “the total number of flowers minus the maximum number of watered flowers”.

Analysis

First, minimizing the number of unwatered flowers is equivalent to maximizing the number of watered flowers. Since the total number of flowers \(\text{total}\) is constant, we have:

\[ (\text{minimum unwatered flowers}) = \text{total} - (\text{maximum watered flowers}) \]

Therefore, the problem reduces to maximizing the number of flowers that fall within a window \([s, s+D)\) of length \(D\).

Another crucial observation is that it is sufficient to consider the sprinkler’s starting position \(s\) to be aligned with the coordinate of one of the flower beds. This is because if the leftmost flower bed inside the interval is \(X_i\), setting \(s\) to be strictly less than \(X_i\) will not increase the number of flowers we can water; instead, it only increases the chance of missing other flower beds on the right. Therefore, we can set each flower bed \(X_i\) as the left end of the interval, calculate “the sum of flowers in the flower beds satisfying \(X_i \leq X_j < X_i + D\)”, and find the maximum value among them.

A naive approach that recounts the flower beds in the interval for each \(i\) would take \(O(N^2)\) time, which will result in a TLE since \(N \leq 2 \times 10^5\). Thus, we can optimize this using the two pointers technique.

Algorithm

We leverage the fact that the coordinates \(X_i\) are already given in ascending order.

We move the left pointer \(i\) from \(0\) to \(N-1\), and for each \(i\), we maintain the right pointer \(j\) (the position just past the last element included in the interval). The key point is that as \(i\) moves to the right, the right pointer \(j\) satisfying the condition \(X_j < X_i + D\) also only moves monotonically to the right and never moves backward.

The detailed procedure is as follows:

1. Prepare cur (the sum of flowers in the current interval) and best (the maximum sum found so far).
2. Increment the left pointer \(i\) starting from \(0\).
3. Advance the right pointer \(j\) to the right as long as \(X_j < X_i + D\) is satisfied, adding \(P_j\) to cur each time it advances.
4. At this point, cur represents the total number of flowers in the window \([X_i, X_i + D)\), so update best.
5. Before moving to the next left pointer, subtract the flowers of the leftmost bed \(P_i\) from cur.

By doing this, since both \(i\) and \(j\) only move in one direction, addition and subtraction operations for each flower bed are performed at most once.

Finally, output total - best.

Simple Example

For example, suppose \(D = 5\) and the flower beds are located at coordinates \(1, 3, 6, 8\). - If the left end is at \(X=1\), the interval is \([1, 6)\), which contains coordinates \(1\) and \(3\). - If the left end is at \(X=3\), the interval is \([3, 8)\), which contains coordinates \(3\) and \(6\). - If the left end is at \(X=6\), the interval is \([6, 11)\), which contains coordinates \(6\) and \(8\).

As the left end moves forward, the right end also moves to the right, which means the two pointers technique can be directly applied.

Complexity

• Time Complexity: \(O(N)\) (Linear, even including reading the input as no sorting is required. \(i\) and \(j\) each advance at most \(N\) times.)
• Space Complexity: \(O(N)\) (Arrays to store coordinates and flower counts.)

Key Implementation Points

• Note that the interval treats \(s + D\) as “strictly less than”. The condition is \(X_j < X_i + D\), not \(\leq\). In the code, we use a strict inequality X[j] < X[i] + D.

• Since the values can be large (the total sum of flowers can be up to around \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\)), you need to be mindful of 64-bit integer limits. In Python, you do not need to worry about this because integers have arbitrary precision, but in other languages, you should use long long.

• Since the input size is large, reading it all at once with sys.stdin.buffer.read() is fast.

• By performing cur -= P[i] at the end of each loop, we maintain the sum for the next loop where the left end has shifted one step to the right. The right pointer \(j\) can resume from its current position, avoiding redundant calculations.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    X = [0]*N
    P = [0]*N
    for i in range(N):
        X[i] = int(data[idx]); idx += 1
        P[i] = int(data[idx]); idx += 1
    
    total = sum(P)
    
    best = 0
    cur = 0
    j = 0
    for i in range(N):
        if j < i:
            j = i
            cur = 0
        # ensure j covers from X[i]
        # remove? not needed since left moves forward
        while j < N and X[j] < X[i] + D:
            cur += P[j]
            j += 1
        if cur > best:
            best = cur
        cur -= P[i]
    
    print(total - best)

main()

---

This editorial was generated by claude4.8opus-high.