# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
167824 | juggernaut | Divide and conquer (IZhO14_divide) | C++14 | 50 ms | 1528 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long int
using namespace std;
struct data{
int x,g,d;
};
data a[100001];
int n,i,l,r,x,g,mx,d,cnt=1;
main(){
scanf("%lld",&n);
cin>>a[1].x>>a[1].g>>a[1].d;
for(i=2;i<=n;i++)
{
scanf("%lld%lld%lld",&x,&g,&d);
if(a[cnt].x + a[cnt].d >= x){
a[cnt].d+=d;
a[cnt].g+=g;
}
else{
cnt++;
a[cnt].x=x;
a[cnt].d=d;
a[cnt].g=g;
}
}
n=cnt;
l=r=1;
x=a[1].x;
g=a[1].g;
d=a[1].d;
while(r<=n&&l<=n){
if(r<n&&d+a[r+1].d>=a[r+1].x-x){
r++;
d+=a[r].d;
g+=a[r].g;
mx=max(mx,g);
}else{
g-=a[l].g;
d-=a[l].d;
l++;
x=a[l].x;
}
}
l=r=n;
x=a[n].x;
g=a[n].g;
d=a[n].d;
while(r>0&&l>0){
if(l>0&&d+a[l-1].d>=x-a[l-1].x){
l--;
d+=a[l].d;
g+=a[l].g;
mx=max(mx,g);
}else{
g-=a[r].g;
d-=a[r].d;
r--;
x=a[r].x;
}
}
printf("%lld",mx);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |