Submission #1189575

#TimeUsernameProblemLanguageResultExecution timeMemory
1189575diyah999Divide and conquer (IZhO14_divide)C++20
17 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    ll n;
    cin >> n;

    vector<ll> x(n), g(n), d(n);

    for (ll i = 0; i < n; ++i)
        cin >> x[i] >> g[i] >> d[i];

    ll j = -1, ans = 0, totalEnergy = 0, totalGold = 0;

    for (ll i = 0; i < n; ++i) {
        if (i != 0) {
            totalEnergy -= d[i - 1];
            totalGold -= g[i - 1];
        }

        while (j + 1 < n && totalEnergy + d[j + 1] >= x[j + 1] - x[i]) {
            ++j;
            totalEnergy += d[j];
            totalGold += g[j];
        }

        ans = max(ans, totalGold);
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...