Submission #1352573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352573		nathlol2	Fuel Station (NOI20_fuelstation)	C++20	13 / 100	299 ms	26956 KiB

FuelStation

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, d;
tuple<int, int, int> a[N];

bool ok(int x){
    vector<tuple<int, int, int>> v;
    v.push_back({0, 0, 0});
    for(int i = 1;i<=n;i++){
        if(get<2>(a[i]) >= x) v.push_back(a[i]);
    }
    int cur = x;
    v.push_back({d, 0, 0});
    for(int i = 1;i<v.size();i++){
        cur -= (get<0>(v[i]) - get<0>(v[i - 1]));
        if(cur < 0) return 0;
        cur += get<1>(v[i]);
    }
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> d;
    for(int i = 1;i<=n;i++){
        auto &[x, b, c] = a[i];
        cin >> x >> b >> c;
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = d, ans = -1;
    while(l <= r){
        int md = (l + r) / 2;
        if(ok(md)){
            ans = md;
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    cout << ans;
}

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