Submission #341518

#	Time	Username	Problem	Language	Result	Execution time	Memory
341518		ogibogi2004	Bigger segments (IZhO19_segments)	C++14	100 / 100	314 ms	41792 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=2e17;
const int MAXN=5e5+6;
ll a[MAXN],n;
ll pref[MAXN];
ll dp[MAXN],s[MAXN];
vector<pair<ll,ll> >v[MAXN];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		pref[i]=pref[i-1]+a[i];
	}
	dp[0]=0;s[0]=0;
	priority_queue<pair<ll,ll> >pq;
	pq.push({0,0});
	priority_queue<pair<pair<ll,ll>,ll> >to_add;
	for(int i=1;i<=n;i++)
	{
		while(!to_add.empty()&&-to_add.top().first.first<=pref[i])
		{
			pq.push({to_add.top().first.second,to_add.top().second});
			to_add.pop();
		}
		auto t=pq.top();
		dp[i]=t.first+1;
		to_add.push({{-2*pref[i]+pref[t.second],dp[i]},i});
	}
	cout<<dp[n]<<endl;
return 0;
}

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