oj.uz

Submission #143619

# Submission time Handle Problem Language Result Execution time Memory
143619 2019-08-14T18:18:11 Z beso123 Bigger segments (IZhO19_segments) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[500005],dp[500005],pref[500005];
int v[500005];
int get(int pos,int k){
return pref[k]-pref[pos];
}
main(){
cin>>n;
for(int k=1;k<=n;k++){
    cin>>a[k];
    pref[k]=pref[k-1]+a[k];
}
v[1]=a[1];
dp[1]=1;
for(int k=2;k<=n;k++){
 
   if(a[k]>=v[k-1]){
    v[k]=a[k];
    dp[k]=dp[k-1]+1;
    continue;
   }
 
   else{
 
    int l=1,r=k-1;
while(r-l>1){
   int mid=(l+r)/2;
   int p=get(mid,k);
   if(v[mid]<=p)
    l=mid;
   else r=mid;
}
int pas=0;
if(v[r]<=get(r,k))
    pas=r;
else{
   if(v[l]<=get(l,k))
        pas=l;
}
if(dp[pas]+1>dp[k-1] && pas!=0){
    dp[k]=dp[pas]+1;
    v[k]=pref[k]-pref[pas];
}
else{
    dp[k]=dp[k-1];
    v[k]=v[k-1]+a[k];
}
   }
 
}
cout<<dp[n];
return 0;
}

Compilation message

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

Subtask #1
0 / 13.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 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 10.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 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 36.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 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.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 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -