Submission #45079

#	Time	Username	Problem	Language	Result	Execution time	Memory
45079		rajarshi_basu	Divide and conquer (IZhO14_divide)	C++14	100 / 100	314 ms	24520 KiB

divide

#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;
        ^~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52