제출 #143619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143619		beso123	Bigger segments (IZhO19_segments)	C++14	0 / 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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