Overview

This problem asks us to optimally place a half-open interval \([s, s+D)\) of length \(D\) on \(N\) flowerbeds on a number line to maximize the number of flowers included in the interval (which is equivalent to minimizing the number of unwatered flowers outside the interval).

Analysis

1. Narrowing down the candidates for the sprinkler position \(s\)

Although the sprinkler position \(s\) can be any real number greater than or equal to \(0\), we cannot search through infinitely many real numbers. Let’s consider the optimal position \(s\).

The watering range of the sprinkler is \([s, s+D)\). Suppose the left end of the watering range \(s\) does not coincide with the coordinate of any flowerbed, and some flowerbeds are included in the interval. In this case, even if we shift the sprinkler’s position to the right so that the left end \(s\) of the interval coincides with the coordinate \(X_i\) of the leftmost flowerbed inside the interval, the number of covered flowerbeds will not decrease. Rather, because we gain extra space on the right, we may cover even more flowerbeds.

Therefore, it is sufficient to consider only the cases where the left end \(s\) of the sprinkler coincides with the coordinate of some flowerbed \(X_i\) (\(s = X_i\)). The candidates for \(s\) to search are narrowed down to \(N\) possibilities: \(s = X_1, X_2, \dots, X_N\).

2. Issues with the Naive Approach (Brute Force)

For each \(s = X_i\), if we check the flowerbeds included in the interval \([X_i, X_i+D)\) one by one to calculate the total number of flowers, it takes \(O(N)\) time per candidate. Doing this for all \(i\) (\(1 \leq i \leq N\)) results in an overall time complexity of \(O(N^2)\). Since the constraint of this problem is \(N \leq 2 \times 10^5\), this approach will not run within the time limit (typically around 2 seconds) and will result in a TLE (Time Limit Exceeded).

3. Idea for Optimization (Using Monotonicity)

The coordinates of the flowerbeds are sorted in ascending order: \(X_1 < X_2 < \dots < X_N\). As we move the left end \(s = X_{\text{left}}\) to the right, the corresponding right boundary \(X_{\text{left}} + D\) also moves to the right. When we have this kind of “monotonicity” where moving the left end only moves the right end further to the right, we can use the Two Pointers technique to avoid redundant calculations and solve the problem efficiently.

Algorithm

Using the two-pointer technique, we can efficiently manage the right end right for each left end left.

1. Initialization:

   • Calculate the sum of all flowers total_flowers beforehand.
   • Initialize the maximum number of flowers in the interval max_sum to \(0\), the current interval sum current_sum to \(0\), and the right pointer right to \(0\).

2. Two-Pointer Loop:

   • Move the left pointer left sequentially from \(0\) to \(N-1\).
   • For each left, increment right by \(1\) and add P[right] to current_sum as long as X[right] < X[left] + D is satisfied.
   • When right can no longer advance, compare the current_sum at that moment with max_sum and update the maximum value.
   • To prepare for the next iteration (moving left forward by \(1\)), subtract the number of flowers at the current left end, P[left], from current_sum.

3. Outputting the Answer:

   • The maximum number of flowers that can be watered is max_sum.
   • Since we want to find the “minimum number of unwatered flowers,” the answer is the total sum minus the maximum value: total_flowers - max_sum.

Walkthrough with a Concrete Example

Consider the case where \(D = 5\), flowerbed coordinates \(X = [1, 2, 5, 7]\), and the number of flowers \(P = [2, 3, 4, 1]\).

• left = 0 (\(X_0 = 1\)):

  • The allowable range is less than \(1 + 5 = 6\).
  • right = 0 (\(X_0=1 < 6\)): Add \(P_0=2\) to current_sum. Advance right to \(1\).
  • right = 1 (\(X_1=2 < 6\)): Add \(P_1=3\) to current_sum. Advance right to \(2\).
  • right = 2 (\(X_2=5 < 6\)): Add \(P_2=4\) to current_sum. Advance right to \(3\).
  • right = 3 (\(X_3=7 \geq 6\)): Out of range, so stop.
  • Current sum current_sum = 9. Update max_sum to \(9\).
  • To advance left, subtract \(P_0=2\) from current_sum to get \(7\).

• left = 1 (\(X_1 = 2\)):

  • The allowable range is less than \(2 + 5 = 7\).
  • right = 3 (\(X_3=7 \geq 7\)): Out of range, so cannot advance.
  • Current sum current_sum = 7.
  • To advance left, subtract \(P_1=3\) from current_sum to get \(4\).

In this way, the right pointer never moves backward and always moves forward to the right, allowing for fast processing.

Complexity

• Time Complexity: \(O(N)\)
  • The left and right pointers each move from one end of the array to the other at most once. Therefore, the total number of steps in the loop is at most \(2N\), making the time complexity \(O(N)\), which is extremely fast. Even in Python, it can easily get AC (Accepted) in around 0.1 seconds.
• Space Complexity: \(O(N)\)
  • Since the sizes of the arrays storing the flowerbed coordinates \(X\) and the number of flowers \(P\) are proportional to \(N\), the space complexity is \(O(N)\).

Implementation Points

• Fast I/O: In Python, when the number of inputs \(N\) is around \(2 \times 10^5\), repeatedly using standard input() can cause I/O to become a bottleneck and lead to TLE. By using sys.stdin.read().split() to read and split all inputs at once, we can significantly speed up I/O.

• Half-Open Interval Condition: The condition in the problem description is “distance less than \(D\),” so the condition for checking the right end is X[right] < X[left] + D (note that it is < and not <=).

  Source Code

import sys


def solve():
    # 入力をすべて高速に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    D = int(input_data[1])

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

    # 1次元リストから X と P を展開
    idx = 2
    for i in range(N):
        X[i] = int(input_data[idx])
        P[i] = int(input_data[idx + 1])
        idx += 2

    total_flowers = sum(P)

    # しゃくとり法を用いて、区間 [X_j, X_j + D) に含まれる花の本数の最大値を求める
    max_sum = 0
    current_sum = 0
    right = 0

    for left in range(N):
        limit = X[left] + D
        while right < N and X[right] < limit:
            current_sum += P[right]
            right += 1

        if current_sum > max_sum:
            max_sum = current_sum

        current_sum -= P[left]

    # 水やりできない花の本数の最小値を出力
    print(total_flowers - max_sum)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.