Submission #216926

#	Time	Username	Problem	Language	Result	Execution time	Memory
216926		keta_tsimakuridze	Bigger segments (IZhO19_segments)	C++14	100 / 100	332 ms	20884 KiB

segments

#include<bits/stdc++.h>
using namespace std;
long long sum[500005],a[500005],m,k,n,bef[500005],cursum,dp[500005],l,r,ans;
int main(){
	cin>>n;
	for(k=1;k<=n;k++){
		cin>>a[k];
		sum[k]=sum[k-1]+a[k];
	}
	
	for(k=1;k<=n;k++){
		bef[k]=max(bef[k],bef[k-1]);
		cursum=sum[k]-sum[bef[k]];
		dp[k]=dp[bef[k]]+1;
		
		l=k; r=n; ans=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(sum[mid]-sum[k]>=cursum){
				r=mid-1; ans=mid;
			}
			else l=mid+1;
		}
		bef[ans]=k;
	}
	cout<<dp[n];
}

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