概要

各植木鉢を左から順に見て、空いている分だけ水を注げるだけ注ぎ、手持ちの水 \(M\) がなくなるまで（または全て見終わるまで）更新後の水量を出力する問題です。

考察

重要なのは「注ぐ順番が固定（1番から順）」であり、各植木鉢に対してやることは「空き容量 \(C_i - S_i\) を上限に、残り水量 \(M\) の範囲で足す」だけだという点です。

• 植木鉢 \(i\) の空きは \(gap = C_i - S_i\)。
• 実際に足せる量は \(add = \min(gap, M)\)。
• 更新後は \(S_i \leftarrow S_i + add\)、残り水は \(M \leftarrow M - add\)。

この操作を植木鉢1から順に1回ずつ行えば、問題文の手順をそのままシミュレーションできます。

素朴に「1リットルずつ」注ぐようなシミュレーションをすると、最悪で \(M\) が \(10^{18}\) なので到底間に合いません（TLE）。
そこで、各植木鉢ごとに「まとめて」注ぐ（\(\min(gap, M)\) を一度に加算する）ことで、植木鉢の個数 \(N\) 回の処理で済ませます。

アルゴリズム

1. 入力で \(N, M\) を受け取る。
2. \(i=1\) から \(N\) まで順に以下を行う：
   • \(gap = C_i - S_i\) を計算する。
   • もし \(M>0\) かつ \(gap>0\) なら、\(add = \min(gap, M)\) を注ぐ。
   • \(S_i\) と \(M\) を更新する：
     \(S_i \leftarrow S_i + add\), \(M \leftarrow M - add\)
   • 更新後の \(S_i\) を答え配列に保存する。
3. 保存した \(S_1, S_2, \dots, S_N\) を1行ずつ出力する。

例：\(M=7\)、植木鉢が \((C,S)=(5,3),(4,4),(10,2)\) のとき
- 1番: 空き \(2\)、\(add=\min(2,7)=2\) → \(S=5\), \(M=5\)
- 2番: 空き \(0\) → そのまま \(S=4\), \(M=5\)
- 3番: 空き \(8\)、\(add=\min(8,5)=5\) → \(S=7\), \(M=0\)
出力は \(5,4,7\) になります。

計算量

• 時間計算量: \(O(N)\)（各植木鉢を1回ずつ処理）
• 空間計算量: \(O(N)\)（出力用に結果を保持。逐次出力なら \(O(1)\) も可能）

実装のポイント

• \(M\) は最大 \(10^{18}\) なので、Python の int を使えば安全に扱えます（他言語なら 64bit 整数が必要）。

• 高速入出力のため sys.stdin.readline を使うと安心です。

• 追加量は必ず add = min(C-S, M) とし、容量超過や \(M\) の負値を防ぎます。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。