oj.uz

Submission #172786

# Submission time Handle Problem Language Result Execution time Memory
172786 2020-01-02T15:47:54 Z itgl Divide and conquer (IZhO14_divide) C++14
100 / 100
 238 ms 7428 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-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+1;
    while(r-l>=2){
      int mid=(l+r)/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
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 4 ms 516 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 11 ms 760 KB Output is correct
12 Correct 12 ms 760 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 632 KB Output is correct
2 Correct 15 ms 964 KB Output is correct
3 Correct 19 ms 1020 KB Output is correct
4 Correct 91 ms 3708 KB Output is correct
5 Correct 109 ms 4008 KB Output is correct
6 Correct 238 ms 6628 KB Output is correct
7 Correct 163 ms 6532 KB Output is correct
8 Correct 168 ms 6392 KB Output is correct
9 Correct 169 ms 6436 KB Output is correct
10 Correct 160 ms 6176 KB Output is correct
11 Correct 177 ms 7160 KB Output is correct
12 Correct 203 ms 7428 KB Output is correct