oj.uz

Submission #172779

# Submission time Handle Problem Language Result Execution time Memory
172779 2020-01-02T15:34:30 Z itgl Divide and conquer (IZhO14_divide) C++14
0 / 100
 213 ms 6532 KB 
#include<bits/stdc++.h>
typedef long long ll;

using namespace std;

ll x[100005];
ll g[100005];
ll d[100005];
ll pos[100005];
pair<ll,ll>vec[100005];
int n;
int main(){
  cin >> n;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>g[i]>>d[i];
    g[i]=g[i]+g[i-1];
    d[i]+=d[i-1];
    vec[i]=(make_pair(d[i]-x[i],i));
  }

  sort(vec+1,vec+n+1);
  for(int i=n;i>0;i--){
    pos[i]=max(pos[i+1],vec[i].second);
  }
  ll res=0;
  for(int i=1;i<=n;i++){
    int mn=d[i-1]-x[i];
    int l=0,r=n;
    if(r-l>0){
      int mid=(l+r+1)/2;
      if(vec[mid].first>=mn) r = mid;
      else l=mid;
    }
    res=max(res,g[pos[r]]-g[i-1]);
  }

  cout << res << endl;


  return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 292 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 3 ms 380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 14 ms 888 KB Output is correct
3 Correct 18 ms 1016 KB Output is correct
4 Correct 88 ms 3704 KB Output is correct
5 Correct 106 ms 3996 KB Output is correct
6 Correct 213 ms 6532 KB Output is correct
7 Correct 152 ms 6380 KB Output is correct
8 Correct 161 ms 6400 KB Output is correct
9 Correct 149 ms 6392 KB Output is correct
10 Incorrect 153 ms 6408 KB Output isn't correct
11 Halted 0 ms 0 KB -