Submission #492688

#	Time	Username	Problem	Language	Result	Execution time	Memory
492688		luka1234	Bigger segments (IZhO19_segments)	C++14	100 / 100	249 ms	20780 KiB

segments

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n;
ll a[500001];
pair<ll,ll> dp[500001];
ll pref[500001];
int main(){
	cin>>n;
	for(int k=1;k<=n;k++){
		cin>>a[k];
		pref[k]=pref[k-1]+a[k];
		dp[k].ff=1e18;
	}
	dp[0].ss=1;
	for(int k=1;k<=n;k++){
		if(dp[k].ff>=dp[k-1].ff+a[k]){
			dp[k].ff=dp[k-1].ff+a[k];
			dp[k].ss=dp[k-1].ss;
		}
		int l=k+1,r=n,indic=0;
		while(l<r){
			int m=(l+r)/2;
			if(pref[m]-pref[k]>=dp[k].ff){
				r=m;
				indic=1;
			}
			else{
				l=m+1;
			}
		}
		if(pref[l]-pref[k]>=dp[k].ff)
		   indic=1;
		if(indic==1){
			dp[l].ff=pref[l]-pref[k];
			dp[l].ss=dp[k].ss+1;
		}
	}
	cout<<dp[n].ss;
    return 0;
}

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