Atcoder解いてみた AtCoder Beginner Contest D - Water Heater

AtCoder Beginner Contest D - Water Heater

問題はこちら

回答

一次元いもす法の練習

#include <limits.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

int N;
long long W;
std::vector<long long> arrSum;

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);

    std::cin >> N >> W;

    arrSum.resize(300000);
    for (int i = 0; i < N; i++) {
        int s, t;
        long long p;
        std::cin >> s >> t >> p;  // 時刻tを除くので、すでに[s,t)

        arrSum[s] += p;
        arrSum[t] -= p;
    }

    for (int i = 1; i < arrSum.size(); i++) {
        arrSum[i] += arrSum[i - 1];
    }

    std::string ans = "Yes";
    for (int i = 0; i < arrSum.size(); i++) {
        if (arrSum[i] > W) {
            ans = "No";
            break;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}