AtCoder Beginner Contest 183 D - Water Heater【Python】

AtCoder

https://atcoder.jp/contests/abc183/tasks/abc183_d

AtCoder ProblemsでDifficulty: 662、Solve Probability: 40%でした。

階差を求めてその累積和を計算しW以上の値があるかを判定していきました。おそらく、いもす法と呼ばれるもののようです。 ​

gihyo.jp

丁度上記の書籍で階差などについて学習したところでした。

N, W = map(int, input().split())
time = 2 * 10 ** 5
D = [0] * (time + 2)
for i in range(N):
    s, t, p = map(int, input().split())
    D[s] += p
    D[t] -= p

sum_D = []
for i in range(time + 2):
    if i == 0:
        w = D[i]
        sum_D.append(w)
    else:
        w = sum_D[i - 1] + D[i]
        sum_D.append(w)

    if w > W:
        print("No")
        exit()
print("Yes")