[AtCoder] ABC 183 D – Water Heater

2020年12月12日

問題

方針

ある時間において使用される水の最大値が \( W \) を超えなければ良いので、いもす法を使います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX = 200005;
ll table[MAX]{};

int main() {
    int N;
    ll W;
    cin >> N >> W;
    int S[N], T[N];
    ll P[N];
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> T[i] >> P[i];
        table[S[i]] += P[i];
        table[T[i]] -= P[i];
    }
    for (int i = 1; i < MAX; i++) {
        table[i] += table[i - 1];
    }
    for (ll i : table) {
        if (i > W) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}