Submission #952680

#	Time	Username	Problem	Language	Result	Execution time	Memory
952680		offlineDeletionTrickFan	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	137 ms	27076 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 5;
struct station {
    int a, b, x;
    bool operator<(const station& other) const {
        return x < other.x;
    }
} v[MAXN];
signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, d;
    cin >> n >> d;
    ++n;
    for (int i = 1; i < n; ++i) cin >> v[i].x >> v[i].a >> v[i].b;
    v[n].a = v[n].b = 0;
    v[n].x = d;
    sort(v + 1, v + n + 1);
    int ans = 0, curf = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 1; i <= n; ++i) {
        if (curf < v[i].x) {
            ans += v[i].x - curf;
            curf = v[i].x;
        }
        while (!pq.empty() && pq.top().first < ans) {
            curf -= pq.top().second; pq.pop();
            if (curf < v[i].x) {
                ans += v[i].x - curf;
                curf = v[i].x;
            }
        }
        if (ans <= v[i].b) {
            curf += v[i].a;
            pq.push({v[i].b, v[i].a});
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21