Submission #708937

#	Time	Username	Problem	Language	Result	Execution time	Memory
708937		amirhoseinfar1385	Bigger segments (IZhO19_segments)	C++17	100 / 100	204 ms	72816 KiB

segments

#include<bits/stdc++.h>
using namespace std;

pair<long long ,long long>comb(pair<long long ,long long>a,pair<long long ,long long>b){
	if(a.first==b.first){
		if(a.second<b.second){
			return a;
		}
		return b;
	}
	if(a.first>b.first){
		return a;
	}
	return b;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<long long>all(n+1);
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	vector<long long>ps(n+1);
	for(int i=1;i<=n;i++){
		ps[i]=all[i]+ps[i-1];
	}	
	set<pair<long long,long long>>st[n+2];
	vector<pair<long long ,long long>>dp(n+1);
	st[0].insert(make_pair(0,0));
	st[1].insert(make_pair(ps[1]*2,1));
	dp[1]=make_pair(1,ps[1]);
	long long k=1;
	for(int i=2;i<=n;i++){
		dp[i]=dp[i-1];
		dp[i].second+=all[i];
		while((int)st[k-1].size()>0){
			auto x=*st[k-1].begin();
			if(x.first<=ps[i]){
				dp[i]=comb(dp[i],make_pair(dp[x.second].first+1,ps[i]-ps[x.second]));
				st[k-1].erase(x);
			}
			else{
				break;
			}
		}
		while((int)st[k].size()>0){
			auto x=*st[k].begin();
			if(x.first<=ps[i]){
				dp[i]=comb(dp[i],make_pair(dp[x.second].first+1,ps[i]-ps[x.second]));
				st[k].erase(x);
			}
			else{
				break;
			}
		}
		k=max(k,dp[i].first);
		st[dp[i].first].insert(make_pair(dp[i].second+ps[i],i));
	}
	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