#include <bits/stdc++.h>
#define ll long long
#define val first
#define ind second
using namespace std;
const int N=1e5+5;
int n,a,b,x;
ll ans;
typedef struct{
int x, gold , energy;
}camp;
vector<camp> v;
vector<pair<ll, int>> mn;
map <int, ll> g, d;
main(){
cin>>n;
for(int i=0; i<n; i++){
cin>>x>>a>>b;
v.push_back({x,a,b});
}
g[0]=v[0].gold; d[0]=v[0].energy;
for(int i=1; i<n; i++){
g[i]=g[i-1]+v[i].gold;
d[i]=d[i-1]+v[i].energy;
}
a=0;
for(int i=0; i<n; i++){
b=i; int mid=0;
if(mn.size()==0 || mn[mn.size()-1].val>d[b-1]-v[b].x){
mn.push_back({d[b-1]-v[b].x,i});
}
int cost=d[b]-v[b].x;
int l=0; int r=mn.size()-1;
while(l<=r){
mid=(l+r)/2;
if(mn[mid].val<=cost) r=mid-1;
else l=mid+1;
}
a=mn[mid].ind;
ans=max(ans, g[b]-g[a-1]);
}
cout<<ans<<endl;
}
Compilation message
divide.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
15 | main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
