Overview

Buckets receive water from the front in order until they are full, and once full, water flows to the next bucket. The problem asks “how many buckets from the front can be completely filled” with a total of \(W\) liters.

Analysis

The key observation is that “water always accumulates in the order bucket \(1 \rightarrow 2 \rightarrow 3 \rightarrow \cdots\).” Until bucket \(i\) is full, all water goes into bucket \(i\), and only once it becomes full does the overflow go to bucket \(i+1\). Therefore, it is impossible for a later bucket to become full while skipping an intermediate bucket.

Thus, the number of buckets that end up full is determined by simply asking:

• Can we fill \(C_1\)?
• If so, can we also fill \(C_2\)?
• ……

In other words, we just count from the front as long as the prefix sum of capacities is at most \(W\).

A naive approach of “simulating 1 liter per second for \(W\) seconds” would never finish in time since \(W \le 10^{18}\) (TLE). However, the concept of time is not essential in this problem — all we need is “how many bucket capacities can we fully pay for with a total of \(W\).”

Example: When \(C=[3,5,2],\ W=8\) The prefix sums are \(3,\ 8,\ 10\), so up to \(8\) covers 2 buckets → 2 buckets are full.

Algorithm

1. Prepare variables total=0 (the amount of water used so far to fill buckets) and ans=0 (the number of full buckets).
2. Iterate through the buckets from the front, letting c be the capacity of the current bucket.
3. If total + c <= W, then this bucket can be filled:
   • total += c
   • ans += 1
4. Otherwise, this bucket cannot be filled, and no subsequent bucket can be filled either (since buckets can only be filled from the front in order), so we break out of the loop.
5. Output ans.

In essence, we are finding “the number of buckets such that the prefix sum of capacities does not exceed \(W\).”

Complexity

• Time complexity: \(O(N)\) (just a single pass from the front)
• Space complexity: \(O(1)\) (only constants besides the input array)

Implementation Notes

• Since \(W \le 10^{18}\), the prefix sum total requires a 64-bit integer (in Python, integers grow automatically, so there’s no concern).

• Breaking as soon as total + c > W avoids unnecessary processing.

• Since the input size can be up to \(2 \times 10^5\), fast input methods like sys.stdin.buffer.read() are effective.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, W = data[0], data[1]
    C = data[2:2+N]

    total = 0
    ans = 0
    for c in C:
        if total + c <= W:
            total += c
            ans += 1
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.