#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)1e5+50;
int n,x[maxn],bit[2*maxn];
long long gold[maxn],energy[maxn];
vector<long long> gt;
void Up(int id,int gt)
{
if(id==0)return;
for(;id<=2*n+2;id+=id&-id)bit[id]=min(bit[id],gt);
}
int Get(int id)
{
if(id==0) return (int)1e6;
int res=(int)1e6;
for(;id>0;id-=id&-id)res=min(res,bit[id]);
return res;
}
int main()
{
cin>>n;
memset(bit,(int)1e6,sizeof(bit));
for(int i=1;i<=n;++i)
{
long long g,d;
cin>>x[i]>>g>>d;
gold[i]=gold[i-1]+g;
energy[i]=energy[i-1]+d;
gt.push_back(energy[i]-x[i]);
gt.push_back(energy[i-1]-x[i]);
}
sort(gt.begin(),gt.end());
gt.erase(unique(gt.begin(),gt.end()));
long long Max=0;
for(int i=1;i<=n;++i)
{
Max=max(Max,gold[i]-gold[i-1]);
int pos=lower_bound(gt.begin(),gt.end(),energy[i]-x[i])-gt.begin()+1;
int l=Get(pos);
if(l!=(int)1e6)Max=max(Max,gold[i]-gold[l-1]);
pos=lower_bound(gt.begin(),gt.end(),energy[i-1]-x[i])-gt.begin()+1;
Up(pos,i);
}
cout<<Max;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
2168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2296 KB |
Output is correct |
2 |
Correct |
3 ms |
2360 KB |
Output is correct |
3 |
Runtime error |
5 ms |
2452 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
2656 KB |
Output is correct |
2 |
Correct |
15 ms |
3080 KB |
Output is correct |
3 |
Runtime error |
17 ms |
3500 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |