Submission #1309157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309157		goduadzesaba	Bigger segments (IZhO19_segments)	C++20	100 / 100	68 ms	15956 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=998244353,inf=1e18;
int _t,n; vector <int> p(N,0); pair<int,int> dp[N];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for (int i=1; i<=n; i++) cin>>p[i],p[i]+=p[i-1];
	for (int i=0; i<=n; i++) dp[i]={1,0};
	for (int i=1; i<=n; i++){
		dp[i]=max(dp[i],dp[i-1]);
		int x=lower_bound(p.begin(),p.begin()+n+1,2*p[i]-p[dp[i].second])-p.begin();
		if (x<=n) dp[x]=max(dp[x],{dp[i].first+1,i});
	//	cout<<x<<" "<<dp[i].first<<" "<<dp[i].second<<"\n";
	} cout<<dp[n].first<<"\n";
}

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