제출 #1369056

#제출 시각아이디문제언어결과실행 시간메모리
1369056werityht1금 캐기 (IZhO14_divide)C++20
0 / 100
0 ms344 KiB
// ???????????????????????????????????????????????????????????
// ???????????????????????????????????????????????????????????
// ???????????????????????????????????????????????????????????
// ???????????????????????????????????????????????????????????
// ???????????????????????????????????????????????????????????
// ???????????????????????????????????????????????????????????
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define tos to_string
#define __lcm(x, y) ((x /__gcd(x, y)) * y)
// #pragma GCC optimize ("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define abs llabs
#define all(v) v.begin(), v.end()
const int N = 2E5 + 5, M = 1E5 + 5, LOG = 30;
const int inf = 1E18, MOD = 1E9 + 7, MOD1 = 998244353;

int t[4 * N]{}, arr[N]{};

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = arr[tl];
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = min(t[v + v], t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r, int need) {
    if (tr < l || r < tl || t[v] > need) return 0;
    if (tl == tr) return tl;
    int tm = (tl + tr) >> 1;
    int res = get(v + v, tl, tm, l, r, need);
    if (res == -1) res = get(v + v + 1, tm+1, tr, l, r, need);
    return res;
}

void solve() {
    int n, ans = 0;
    cin >> n;
    int prefD[n + 1]{}, prefG[n + 1]{}, need[n + 1]{};
    for (int i = 1; i <= n; i++) {
        int x, g, d;
        cin >> x >> g >> d;
        prefD[i] = prefD[i - 1] + d;
        prefG[i] = prefG[i - 1] + g;
        need[i] = prefD[i] - x;
        arr[i] = prefD[i - 1] - x;
    }

    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        int j = get(1, 1, n, 1, i, need[i]);
        if (j != 0) ans = max(ans, prefG[i] - prefG[j - 1]);
        else ans = max(ans, prefG[i] - prefG[i - 1]);
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ttt = 1;
    // cin >> ttt;
    while(ttt--) {
        solve();
    }
}
/*
square
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…