/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
// skibidi rizz
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
#define endl "\n"
#define int ll
#define F first
#define S second
#define db double
#define ld long double
#define short unsigned short
#define pii pair<int,int>
using namespace std;
const ll inf = 1e18,MOD=998244353,N=1e5+10,MN=1e9+7,lim=1e6;
const long db Pie=acos(-1);
//...and justice for all
int binpow(int a,int p);
struct mine{
int x,g,d;
};
mine a[N];
int n;
int ans=0;
void rec(int l,int r){
if(l==r){
ans=max(ans,a[l].g);
return ;
}
int m=(l+r)/2;
rec(l,m);
rec(m+1,r);
int curg=0,cure=0;
vector<pair<int,int>>v;
int last=0;
for(int i=m+1;i<=r;i++){
v.pb({a[i].d-(a[i].x-a[m+1].x),a[i].g+last});
last+=a[i].g;
}
sort(v.begin(),v.end());
// for(int i=0;i<v.size();i++){
// cout<<v[i].F<<' ';
// }
// cout<<endl;
vector<int>suf(v.size()+1,-inf);
for(int i=v.size()-1;i>=0;i--){
suf[i]=max(suf[i+1],v[i].S);
}
for(int i=m;i>=l;i--){
cure+=a[i].d-(a[i+1].x-a[i].x);
// cout<<cure<<" ";
curg+=a[i].g;
int lx=0,rx=v.size()-1;
int res=-1;
while(lx<=rx){
int mid=(lx+rx)/2;
if(-cure<=v[mid].F){
rx=mid-1;
res=mid;
}
else{
lx=mid+1;
}
}
// cout<<endl<<res;
if(res!=-1){
ans=max(ans,suf[res]+curg);
}
}
}
const void solve(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].x>>a[i].g>>a[i].d;
}
rec(0,n-1);
cout<<ans<<endl;
}
main() {
srand(time(NULL));
IOS;
//freopen("c oins.in", "r", stdin);
//freopen("coins.out", "w", stdout);
int UwU=1;
// cin>>UwU;
for(int i=1;i<=UwU;i++) {
// cout<<"Case "<<i<<": ";
solve();
// cout<<endl;
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
// int binmul(int a,int b){}
int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}
Compilation message
divide.cpp:98:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
98 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
