Submission #1263443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263443		sohamsen15	Fuel Station (NOI20_fuelstation)	C++20	13 / 100	131 ms	9308 KiB

FuelStation

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(0);

    ll n, d; cin >> n >> d;
    map<ll, vector<pair<ll, ll>>> stations;
    for (ll i = 0; i < n; i++) {
        ll x, a, b; cin >> x >> a >> b;
        stations[x].push_back({a, b});
    }

    function<bool(ll)> works = [&](ll f) {
        ll curr = f, last = 0;
        bool valid = true;

        for (auto [pos, lst]: stations) {
            if (pos - last <= curr) {
                curr -= pos - last;
                ll mxf = curr;
                for (auto [a, b]: lst) 
                    mxf = max(mxf, curr + a);
                curr = mxf;
                last = pos;
            } else {
                valid = false;
                break;
            }
        }

        if (d - last <= curr && valid) return true;
        return false;
    };

    ll low = 0, high = d;
    ll ans = d;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (works(mid)) ans = min(ans, mid), high = mid - 1;
        else low = mid + 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