oj.uz

Submission #170222

# Submission time Handle Problem Language Result Execution time Memory
170222 2019-12-24T09:31:32 Z beso123 Divide and conquer (IZhO14_divide) C++14
17 / 100
 223 ms 5624 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, pair<int,int> >
#define x first
#define y second.first
#define z second.second
using namespace std;
int n;
pii a[100005];
main(){
cin>>n;
for(int k=1;k<=n;k++){
    int a1,b,c;
    cin>>a1>>b>>c;
   a[k]={a1,{b,c}};
}
int l=1;
int pos=a[1].x,val=0;
int ans=a[1].y,sc=a[1].z;
int pas=ans;
for(int r=1;r<=n;r++){
  if(r!=1){
    ans+=a[r].y;
    sc+=a[r].z;
    val=a[r].x-pos;
  }
  while(l<=r && sc<val){
    ans-=a[l].y;
    sc-=a[l].z;
   pos=a[l+1].x;
    val=max((int)0,a[r].x-pos);
    l++;
  }
  pas=max(pas,ans);
}
cout<<pas;
return 0;
}

Compilation message

divide.cpp:10:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 504 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 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 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
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 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 14 ms 632 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 85 ms 2588 KB Output is correct
5 Correct 103 ms 2972 KB Output is correct
6 Correct 223 ms 5624 KB Output is correct
7 Correct 151 ms 4344 KB Output is correct
8 Correct 157 ms 4520 KB Output is correct
9 Correct 146 ms 4308 KB Output is correct
10 Incorrect 152 ms 4268 KB Output isn't correct
11 Halted 0 ms 0 KB -