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 <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <functional>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define pb(a) push_back(a)
#define vi vector<int>
#define ii pair<int,int>
#define iii pair<bool, pair<int,int> >
#define mp(a,b) make_pair(a,b)
using namespace std;
ll* st;
void init(int n){
st = new ll[4*n];
FOR(i,4*n) st[i] = 0;
}
void update(int node,int ss,int se,int i,ll val){
if(i>se || i<ss)return;
if(ss==se){st[node] = val;return;}
int mid = (ss+se)/2;
update(node*2+1,ss,mid,i,val);
update(node*2+2,mid+1,se,i,val);
st[node] = max(st[node*2+1] , st[node*2+2]);
}
int get(int node,int ss,int se,int qs,int qe,ll param){
if(qe < ss || qs > se)return -1;
// if(st[node]<param)return -1;
if(ss == se){
// cout << " hoha "<< ss << " " << se << " " <<st[node] << " " <<param <<endl;
if(st[node]+param<0)return -1;
else return ss;
}
int mid = (ss+se)/2;
// cout << ss << " " << se << " " << st[node] <<endl;
if(qs <= ss && qe >= se){
if(st[node]+param <0 ){/*cout << "done " << ss << " " <<se << " " << st[node] << " " << param << " " <<endl;*/return -1;}
else{
if(st[2*node+2]+param>=0 ){
return get(node*2+2,mid+1,se,qs,qe,param);
}else if(st[node*2+1]+param>=0){
return get(node*2+1,ss,mid,qs,qe,param);
}
}
}
return max(get(2*node+1,ss,mid,qs,qe,param),get(2*node+2,mid+1,se,qs,qe,param));
}
int main(){
int n;
cin >> n;
init(n);
ll x[n];
ll g[n];
ll d[n];
FOR(i,n)cin >> x[i] >> g[i] >> d[i];
int rel[n];
rel[0] = 0;
FORE(i,1,n-1){
rel[i] = d[i] - x[i] + x[i-1];
}
ll prel[n];//sum from 0 to n;
prel[0] = rel[0];
FORE(i,1,n-1)prel[i] = prel[i-1] + rel[i];
FOR(i,n){
update(0,0,n-1,i,prel[i]);
}
// cout <<" uu "<<endl;
ll pg[n];
// FOR(i,n)cout << rel[i] <<" ";cout<<endl;
//FOR(i,n)cout << prel[i] <<" ";cout<<endl;
pg[0] = g[0];
FORE(i,1,n-1)pg[i] = pg[i-1] + g[i];
// FOR(i,n)cout << pg[i] << " ";cout<<endl;
ll mx = g[n-1];
FOR(i,n-1){
ll sum = 0;
ll gc = g[i];
if(d[i]>=0)mx = max(mx,gc);
//cout << i <<" " << -prel[i] + d[i] <<endl;
int ln = get(0,0,n-1,i+1,n-1,-prel[i] + d[i]);
//cout << "ln : " << ln <<endl;
if(ln!=-1)
mx = max(mx,pg[ln] - ((i==0)?0:pg[i-1]));
}
cout << mx<<endl;
}
Compilation message (stderr)
divide.cpp: In function 'int main()':
divide.cpp:90:8: warning: unused variable 'sum' [-Wunused-variable]
ll sum = 0;
^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |