Overview

There are \(N\) buckets, and water flows into them sequentially starting from the first. When each bucket becomes full, the water flows into the next bucket. Given that a total of \(W\) liters of water flows in, find the number of buckets that are ultimately full.

Analysis

In this problem, water flows starting from bucket \(1\), and when a bucket becomes full, the water flows into the next bucket. Therefore, it seems like we could simulate how much water each bucket receives from front to back. However, looking at the constraints, \(W\) can be as large as \(10^{18}\), so a simulation that adds water one liter at a time is not practical (it would result in TLE).

Instead, for the question “how many buckets are ultimately full?”, we consider “the amount of water needed for all buckets up to the \(k\)-th one to be completely full”. This can be computed using prefix sums of the bucket capacities. That is, for the first \(k\) buckets to all be full, \(C_1 + C_2 + \cdots + C_k\) liters of water are needed.

Computing this naively for all \(k\) is also inefficient, so we use the technique of prefix sums + binary search. Specifically, we prepare a prefix sum array \(S\) such that \(S[k] = C_1 + \cdots + C_k\). Then, we use binary search to find the maximum \(k\) such that \(S[k] < W\).

Furthermore, even if the last bucket is not full, there may be a case where it is partially filled, so we adjust the final answer to account for this.

Algorithm

1. Construct the prefix sum array \(S\) from each bucket’s capacity \(C_i\).
   \(S[i] = C_1 + C_2 + \cdots + C_i\)

2. Using binary search, find “the maximum number of buckets for which the total water needed to fill them all is less than \(W\)”.

   • Condition: \(S[\text{mid}] < W\)

3. In addition to the obtained number of buckets, check whether a “partially filled bucket” exists at the next position.

   • If \(S[\text{answer}] + C[\text{answer}] \leq W\), then that bucket is also full, so add +1 to the answer.

Complexity

• Time complexity: \(O(N)\) (prefix sum computation) + \(O(\log N)\) (binary search) → Overall \(O(N + \log N) = O(N)\)
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• sys.stdin.read is used to read input quickly.
• By precomputing prefix sums, the sum of any range can be obtained in constant time.
• Pay attention to the termination condition and update method of the binary search, and also consider boundary cases (for example, when all buckets become full).

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    W = int(data[1])
    C = list(map(int, data[2:]))

    # 累積和を計算
    S = [0] * (N + 1)
    for i in range(N):
        S[i + 1] = S[i] + C[i]

    # 二分探索で満杯になるバケツの数を求める
    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if S[mid] < W:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    # 最後に部分的に満たされるバケツがあるか判定
    if answer < N and S[answer] + C[answer] <= W:
        answer += 1

    print(answer)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.