Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const long long INF = (long long)(1e18);

long long x[N], g[N], r[N];
long long sumG[N], sumR[N];

int n;

void initialize() {
    for (int i = 1; i <= n; ++i) {
        sumG[i] = sumG[i - 1] + g[i];
        sumR[i] = sumR[i - 1] + r[i];
    }
}

long long naive() {
    long long ans = 0;
    for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) {
        if (sumR[j] - sumR[i - 1] >= x[j] - x[i]) {
            ans = max(ans, sumG[j] - sumG[i - 1]);
        }
    }
    return ans;
}

vector<long long> V;

int getIndex(long long v) {
    return lower_bound(V.begin(), V.end(), v) - V.begin() + 1;
}

long long BIT[N];

void update(int i, long long v) {
    for (; i < N; i += i & -i) BIT[i] = max(BIT[i], v);
}

long long getMax(int i) {
    long long ans = -INF;
    for (; i; i -= i & -i) ans = max(ans, BIT[i]);
    return ans;
}

long long fullSolution() {
    for (int i = 0; i < N; ++i) BIT[i] = -INF;
    for (int i = 1; i <= n; ++i) {
        V.push_back(sumR[i] - x[i]);
        V.push_back(sumR[i - 1] - x[i]);
    }
    sort(V.begin(), V.end());
    V.resize(unique(V.begin(), V.end()) - V.begin());
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        update(getIndex(sumR[i - 1] - x[i]), -sumG[i - 1]);
        long long cur = getMax(getIndex(sumR[i] - x[i])) + sumG[i];
        ans = max(ans, cur);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> g[i] >> r[i];
    initialize();
    //long long correctAnswer = naive();
    long long myAnswer = fullSolution();
    //assert(correctAnswer == myAnswer);
    //cerr << correctAnswer << endl;
    cout << myAnswer << endl;
    return 0;
}