# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1241013 | _dtq_ | 금 캐기 (IZhO14_divide) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (ll)(x.size())
#define all(v) v.begin(), v.end()
#define sz(x) (ll)(x.size())
#define se second
#define fi first
using namespace std;
const ll N = 4e5 + 9;
ll n, i, x[N], y[N], z[N], pre[N], bit[N], gold[N];
void up(ll x, ll val)
{
while(x <= n * 4)
{
bit[x] = max(bit[x], val);
x += (x & (-x));
}
}
ll get( ll x )
{
if(x == 0) return 0;
ll sum = -1e18;
while(x > 0)
{
sum = max(sum, bit[x]);
x -= (x & (-x));
}
return sum;
}
vector<ll>vec;
int main()
{
#define TN "divide"
if (fopen(TN ".in", "r"))
{
freopen(TN ".in", "r", stdin);
freopen(TN ".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n;
ll sum = 0;
for( i = 1; i <= n; i ++ )
{
cin >> x[i] >> y[i] >> z[i];
bit[i] = -1e18;
pre[i] = pre[i - 1] + z[i];
gold[i] = gold[i - 1] + y[i];
vec.pb(pre[i] - x[i]);
vec.pb(pre[i - 1] - x[i]);
}
vec.pb(-1e18);
sort(all(vec));
ll kq = 0;
ll maxn = 0, save = 0;
for( i = 1; i <= n; i ++ )
{
ll k = pre[i] - x[i];
ll vt = lower_bound(all(vec), k) - vec.begin();
ll ans = get(vt);
ll old = max(ans, 0LL);
ans += gold[i];
kq = max({kq, y[i], ans});
ans = max(ans. y[i]);
old -= gold[i - 1];
vt = lower_bound(all(vec), pre[i - 1] - x[i]) - vec.begin();
up(vt, old);
}
cout << kq;
return 0;
}
/*
6
0 5 1
1 7 2
4 4 1
7 15 1
8 15 0
10 15 2
5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
*/