Overview

By choosing the sprinkler’s position optimally, we maximize the number of flowers contained in the half-open interval \([s, s+D)\) of length \(D\).
The answer is the “total number of flowers” minus the “maximum number of watered flowers”.

Analysis

If we place the sprinkler at coordinate \(s\), the watered flowerbeds are those contained in

\([s, s+D)\).

In other words, this problem can be rephred as follows:

Given points \(X_i\) on a number line with weights \(P_i\), find the maximum sum of weights contained in a half-open interval of length \(D\).

If we denote this maximum value as best, the number of unwatered flowers is

\(total - best\).

Here is an important observation:

Although the sprinkler’s position \(s\) is a real number, we can assume that the optimal position is at the coordinate of “some flowerbed”.

Suppose there are flowerbeds watered at some position \(s\).
Let \(X_l\) be the leftmost flowerbed among them. If we shift the left end of the interval to the right from \(s\) to \(X_l\), there are no previously watered flowerbeds in between.
Furthermore, since the right end also shifts to the right by the same amount, we do not lose any flowerbeds, and we might even include new ones.

Therefore, it is sufficient to check only the cases where each flowerbed \(X_l\) is the left end of the interval.

Naively searching for flowerbeds within a distance less than \(D\) for each \(l\) would take \(O(N^2)\) time in the worst case, which will not run in time for \(N \leq 2 \times 10^5\).
Therefore, utilizing the fact that the coordinates are sorted in ascending order, we can solve this efficiently using the two-pointer technique.

Algorithm

Let the left end of the interval be \(X_l\).
The watered flowerbeds are those satisfying

\(X_l \leq X_i < X_l + D\).

We manage the flowerbeds contained in the interval using the half-open index interval \([l, r)\), where \(r\) is the index of the right end.

• \(l\): the current leftmost flowerbed
• \(r\): the first position that no longer satisfies the condition \(X_r < X_l + D\)
• cur: the current total number of flowers in the interval \([l, r)\)
• best: the maximum value of cur found so far

Specifically, we perform the following process for each \(l\):

1. Set limit = X[l] + D.
2. While \(r < N\) and \(X_r < limit\), increment \(r\) to the right and add \(P_r\) to cur.
3. At this point, cur represents the number of flowers contained in the interval \([X_l, X_l + D)\).
4. Update best.
5. To move to the next \(l\), subtract the current leftmost value \(P_l\) from cur.

Since \(r\) never moves backward once it advances, it moves at most \(N\) times in total.
Thus, it can be calculated very quickly.

For example, consider the case where \(D=4\) and the coordinates of the flowerbeds are \(1, 3, 5, 8\).

If we set the left end to \(1\), the interval is \([1, 5)\), so coordinates \(1, 3\) are included.
Coordinate \(5\) is exactly at the right boundary, so it is not included in \([1, 5)\).
As shown here, care must be taken that the condition is “less than \(D\)” rather than “less than or equal to \(D\)”.

Complexity

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

Implementation Points

• Since the interval is \([s, s+D)\), the condition for the right boundary is X[r] < X[l] + D. Do not use <=.

• Since the total number of flowers can be up to \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), a 64-bit integer type is required in languages like C++. In Python, there is no need to worry about integer overflow.

• Note that the final output should be the minimum number of unwatered flowers, not the maximum number of watered flowers, so output total - best.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    D = data[1]

    X = [0] * N
    P = [0] * N
    total = 0

    idx = 2
    for i in range(N):
        x = data[idx]
        p = data[idx + 1]
        X[i] = x
        P[i] = p
        total += p
        idx += 2

    r = 0
    cur = 0
    best = 0

    for l in range(N):
        limit = X[l] + D
        while r < N and X[r] < limit:
            cur += P[r]
            r += 1
        if cur > best:
            best = cur
        cur -= P[l]

    print(total - best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.