Submission #45063

#TimeUsernameProblemLanguageResultExecution timeMemory
45063rajarshi_basuDivide and conquer (IZhO14_divide)C++14
48 / 100
1073 ms4824 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,ll param){ if(st[node]+param<0){ return -1; }else if(ss==se){ return ss; }else{ int mid = (ss+se)/2; return max(get(2*node+1,ss,mid,param),get(node*2+2,mid+1,se,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 mx = 0; FOR(i,n){ ll sum = 0; ll gc = g[i]; if(sum + d[i]>=0)mx = max(mx,gc); FORE(j,i+1,n-1){ sum += rel[j]; gc+=g[j]; if(sum + d[i] >=0)mx = max(mx,gc); } } cout << mx<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...