Submission #951745

#	Time	Username	Problem	Language	Result	Execution time	Memory
951745		MohammadAbduljalil	Fuel Station (NOI20_fuelstation)	C++17	13 / 100	275 ms	25960 KiB

FuelStation

#include <bits/stdc++.h>
#define fast_input_output() ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
using namespace std;
typedef long long ll;
long long const mod = 1e9 + 7;
ll n, d; vector<vector<ll>> v;
bool check(ll f) {
    for (int i = 0; i < n; i++) {
        ll x = v[i][0], a = v[i][1], b = v[i][2];
        if (f < x - (i ? v[i - 1][0] : 0)) return false;
        if (f <= b) f += a;
    }
    return (f >= d - v.back()[0]);
}
int main() {
    fast_input_output();
    cin >> n >> d; v.resize(n, vector<ll>(3, 0));
    for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1] >> v[i][2];
    sort(v.begin(), v.end());
    ll l = v.front().front(), r = 1000000000ll, mid, res = INT_MAX;
    while (l <= r) {
        mid = ((l + r) >> 1);
        if (check(mid)) {
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
    cout << res;
    return 0;
}

• 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