제출 #1134668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134668		tuongll	금 캐기 (IZhO14_divide)	C++20	100 / 100	52 ms	4064 KiB

divide

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>
#include <array>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mxn = 1e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 3e18;
/*
find segment [l, r] such that:
x[r] - x[l] <= d[l] + d[l + 1] + ... + d[r] = pref_d[r] - pref_d[l - 1]
g[l] + g[l + 1] + ... + g[r] = pref_g[r] - pref_g[l - 1] is max
x[r] - x[l] <= pref_d[r] - pref_d[l - 1]
<=> -(x[r] - pref_d[r]) >= -(x[l] - pref_d[l - 1]) (l <= r)
iterate i from 1 to n, query sth, then add point
x[i] - pref_d[i - 1] with weight pref_g[i - 1]
*/
void solve(){
    int n; cin >> n;
    vector<int> x(n + 1);
    vector<ll> pref_g(n + 1), pref_d(n + 1);
    vector<ll> compress;
    for (int i = 1, g, d; i <= n; ++i){
        cin >> x[i] >> g >> d;
        pref_g[i] = pref_g[i - 1] + g;
        pref_d[i] = pref_d[i - 1] + d;
        compress.push_back(pref_d[i - 1] - x[i]);
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), end(compress));
    vector<ll> bit(n + 1, inf64);
    auto update = [&](int i, ll val){
        for (; i <= n; i += i & -i)
            bit[i] = min(bit[i], val);
    };
    auto get = [&](int i){
        ll res = inf64;
        for (; i; i -= i & -i)
            res = min(res, bit[i]);
        return res;
    };
    ll res = 0;
    for (int i = 1; i <= n; ++i){
        int id = lower_bound(all(compress), pref_d[i - 1] - x[i]) - begin(compress) + 1;
        update(id, pref_g[i - 1]);
        id = upper_bound(all(compress), pref_d[i] - x[i]) - begin(compress);
        res = max(res, pref_g[i] - get(id));
    }
    cout << res;
}
int main(){
	auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
    cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

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