Overview

This problem asks you to look at each flowerpot from left to right, pour as much water as the available capacity allows, and output the updated water amount for each pot until your remaining water \(M\) runs out (or until all pots have been processed).

Analysis

The key observation is that “the order of pouring is fixed (sequentially from pot 1),” and for each flowerpot, all you need to do is “add water up to the available capacity \(C_i - S_i\), limited by the remaining water \(M\).”

• The available capacity of flowerpot \(i\) is \(gap = C_i - S_i\).
• The actual amount you can pour is \(add = \min(gap, M)\).
• After updating: \(S_i \leftarrow S_i + add\), and the remaining water becomes \(M \leftarrow M - add\).

By performing this operation once for each flowerpot sequentially from pot 1, you can directly simulate the procedure described in the problem statement.

If you naively simulate pouring “one liter at a time,” it would never finish in time since \(M\) can be up to \(10^{18}\) in the worst case (TLE). Instead, by pouring “all at once” for each flowerpot (adding \(\min(gap, M)\) in a single step), the entire process completes in just \(N\) iterations, one per flowerpot.

Algorithm

1. Read \(N, M\) from input.
2. For \(i=1\) to \(N\), do the following:
   • Compute \(gap = C_i - S_i\).
   • If \(M>0\) and \(gap>0\), pour \(add = \min(gap, M)\).
   • Update \(S_i\) and \(M\): \(S_i \leftarrow S_i + add\), \(M \leftarrow M - add\)
   • Store the updated \(S_i\) in the answer array.
3. Output the stored \(S_1, S_2, \dots, S_N\), one per line.

Example: \(M=7\), flowerpots are \((C,S)=(5,3),(4,4),(10,2)\) - Pot 1: available capacity \(2\), \(add=\min(2,7)=2\) → \(S=5\), \(M=5\) - Pot 2: available capacity \(0\) → unchanged \(S=4\), \(M=5\) - Pot 3: available capacity \(8\), \(add=\min(8,5)=5\) → \(S=7\), \(M=0\) The output is \(5,4,7\).

Complexity

• Time complexity: \(O(N)\) (each flowerpot is processed exactly once)
• Space complexity: \(O(N)\) (to store results for output; \(O(1)\) is also possible with immediate output)

Implementation Notes

• Since \(M\) can be up to \(10^{18}\), using Python’s int handles it safely (in other languages, a 64-bit integer type is required).

• For fast I/O, it is recommended to use sys.stdin.readline.

• Always compute the added amount as add = min(C-S, M) to prevent exceeding the capacity or making \(M\) negative.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    res = []
    for _ in range(N):
        C, S = map(int, input().split())
        if M > 0:
            gap = C - S
            if gap > 0:
                add = gap if M >= gap else M
                S += add
                M -= add
        res.append(S)
    sys.stdout.write("\n".join(map(str, res)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.