Overview

This is a simulation problem where we pour water into flowerpots in order, refilling each flowerpot to satisfy its remaining capacity.

Analysis

This can be solved by directly simulating the operations described in the problem. For each flowerpot, we calculate its current remaining capacity and pour water while comparing it with the amount of water left. The key points are that we pour water in order starting from the flowerpot with the smallest number, and we continue the operation until either all the water is used up or all the flowerpots have been processed.

From the constraints, \(N\) can be as large as \(2 \times 10^5\), but since the operation for each flowerpot involves only simple calculations, it can be processed in linear time.

Algorithm

1. Read the input values \(N\), \(M\), and for each flowerpot its capacity \(C_i\) and current water amount \(S_i\)
2. Initialize the remaining water amount remaining to \(M\)
3. Process each flowerpot \(i\) (\(0 \leq i < N\)) in order:
   • Calculate the available space space = C[i] - S[i]
   • If remaining is less than or equal to space:
     • Add remaining to the current flowerpot
     • Set remaining to 0
   • Otherwise:
     • Fill the current flowerpot to full capacity (\(C[i]\))
     • Subtract space from remaining
4. Output the final water amount of each flowerpot

Complexity

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

Implementation Notes

• Since we handle large numbers (\(M\) can be up to \(10^{18}\)), be careful about integer overflow (in Python, this is not an issue since arbitrary-precision integers are handled automatically)

• Read input data efficiently

• Process each flowerpot in order while updating the remaining water amount

• Once the water runs out, do not pour water into any subsequent flowerpots

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    M = int(data[1])
    idx = 2
    C = []
    S = []
    for i in range(n):
        c = int(data[idx])
        s = int(data[idx+1])
        idx += 2
        C.append(c)
        S.append(s)
    
    remaining = M
    for i in range(n):
        space = C[i] - S[i]
        if remaining <= space:
            S[i] += remaining
            remaining = 0
        else:
            S[i] = C[i]
            remaining -= space
    
    for s in S:
        print(s)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.