Submission #143136

#	Time	Username	Problem	Language	Result	Execution time	Memory
143136		beso123	Bigger segments (IZhO19_segments)	C++14	13 / 100	2 ms	376 KiB

segments

#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 (stderr)

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

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27