Submission #501472

#	Time	Username	Problem	Language	Result	Execution time	Memory
501472		Mazaalai	Bigger segments (IZhO19_segments)	C++17	100 / 100	82 ms	10080 KiB

segments

#include <bits/stdc++.h> 
using namespace std; 
#define N 500005 
long long pre[N];int n,m,nums[N],dp[N],par[N],id,i;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;m=n+1;for(i=1;i<m;i++)cin>>nums[i],pre[i]+=pre[i-1]+nums[i];for(i=1;i<m;i++){int&p=par[i];p=max(p,par[i-1]);dp[i]=dp[p]+1;id=lower_bound(pre,pre+m,pre[i]*2-pre[p])-pre;par[id]=max(par[id],i);}cout<<dp[n]<<'\n';}

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