Submission #45079

#TimeUsernameProblemLanguageResultExecution timeMemory
45079rajarshi_basuDivide and conquer (IZhO14_divide)C++14
100 / 100
314 ms24520 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...