Edit

【pythonでABC183を解説】D - Water Heater

問題概要

問題ページ

D - Water Heater
D - Water Heater

問題ページへ移動する

問題文

給湯器が \(1\) つあり、毎分 \(W\) リットルのお湯を供給することができます。

\(N\) 人の人がいます。\(i\) 番目の人は時刻 \(S_i\) から \(T_i\) までの間 (時刻 \(T_i\) ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 \(P_i\) リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。

すべての人に計画通りにお湯を供給することはできますか？

制約

  • \(1\leq N \leq 2\times 10^5\)
  • \(0\leq S_i < T_i \leq 2\times 10^5\)
  • \(1\leq W, P_i \leq 10^9\)
  • 入力はすべて整数

問題の考察

ACコード

import sys
import itertools


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, w = list(map(int, input().rstrip('\n').split()))
    ls = [0] * (10 ** 5 * 3)
    for i in range(n):
        s, t, p = list(map(int, input().rstrip('\n').split()))
        ls[s] += p
        ls[t] -= p
    ls = list(itertools.accumulate(ls))
    for i in range(len(ls)):
        if ls[i] > w:
            print("No")
            exit()
    print("Yes")


if __name__ == '__main__':
    solve()

-Edit
-