Submission #1189575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189575		diyah999	Divide and conquer (IZhO14_divide)	C++20	17 / 100	0 ms	328 KiB

divide

#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;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52