oj.uz

Submission #45079

# Submission time Handle Problem Language Result Execution time Memory
45079 2018-04-11T07:07:05 Z rajarshi_basu Divide and conquer (IZhO14_divide) C++14
100 / 100
 314 ms 24520 KB 
#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

divide.cpp: In function 'int main()':
divide.cpp:90:8: warning: unused variable 'sum' [-Wunused-variable]
     ll sum = 0;
        ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 2 ms 476 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 496 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 624 KB Output is correct
11 Correct 3 ms 624 KB Output is correct
12 Correct 15 ms 624 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 6 ms 636 KB Output is correct
6 Correct 4 ms 636 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 5 ms 700 KB Output is correct
10 Correct 4 ms 764 KB Output is correct
11 Correct 10 ms 892 KB Output is correct
12 Correct 11 ms 892 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 892 KB Output is correct
2 Correct 15 ms 1276 KB Output is correct
3 Correct 20 ms 1276 KB Output is correct
4 Correct 113 ms 4348 KB Output is correct
5 Correct 98 ms 5756 KB Output is correct
6 Correct 221 ms 12436 KB Output is correct
7 Correct 191 ms 14340 KB Output is correct
8 Correct 176 ms 16268 KB Output is correct
9 Correct 179 ms 18024 KB Output is correct
10 Correct 314 ms 19776 KB Output is correct
11 Correct 305 ms 21972 KB Output is correct
12 Correct 186 ms 24520 KB Output is correct