#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;
const int nmax=100005;
long long aib[nmax],x[nmax],d[nmax],g[nmax],norm[nmax];
long long sum,sumGold,ans;
int n,i,j;
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,long long val)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx]=max(aib[idx],val);
}
long long compute(int poz)
{
long long ret=LLONG_MIN;
for(int idx=poz;idx>0;idx-=lbit(idx))
ret=max(ret,aib[idx]);
return ret;
}
int pos(long long val)
{
int ret=0;
for(int p=17;p>=0;p--)
if(ret+(1<<p)<=n&&norm[ret+(1<<p)]<=val)
ret+=(1<<p);
return ret;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>x[i]>>g[i]>>d[i];
norm[i]=1LL*sum-x[i];
sum+=d[i];
aib[i]=LLONG_MIN;
}
sort(norm+1,norm+n+1);
sum=0;sumGold=0;
for(i=1;i<=n;i++)
{
update(pos(sum-x[i]),-sumGold);
sum+=d[i];sumGold+=g[i];
ans=max(ans,sumGold+compute(pos(sum-x[i])));
for(j=1;j<=n;j++)
cout<<aib[j]<<' ';
cout<<'\n';
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
1012 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1103 ms |
144484 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |