#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 = 1e5 + 9;
ll n, i, x[N], y[N], z[N], pre[N], bit[N][3], gold[N];
vector<pair<ll,ll>>vec;
void up(ll x, ll c, ll val)
{
while(x <= n)
{
bit[x][c] = max(bit[x][c], val);
x += (x & (-x));
}
}
ll get( ll x, ll c )
{
if(x == 0) return 0;
ll sum = -1e18;
while(x > 0)
{
sum = max(sum, bit[x][c]);
x -= (x & (-x));
}
return sum;
}
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;
ll kq = 0;
for( i = 1; i <= n; i ++ )
{
cin >> x[i] >> y[i] >> z[i];
gold[i] = gold[i - 1] + y[i];
sum += z[i];
vec.pb({sum - x[i], i});
bit[i][0] = -1e18;
bit[i][1] = -1e18;
kq = max(kq, y[i]);
}
sort(all(vec));
for(auto k : vec)
{
i = k.se;
ll ans = get(i - 1, 0);
ans += gold[i];
ans = max(ans, get(i - 1, 1));
ans = max(ans, 0LL);
if(k.fi >= 0) ans = max(ans, gold[i]);
up(i, 1, ans);
up(i, 0, max(0LL, get(i - 1, 1)) - gold[i - 1]);
}
cout << max(kq, get(n, 1));
return 0;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/
Compilation message (stderr)
divide.cpp: In function 'int main()':
divide.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(TN ".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
divide.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | freopen(TN ".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |