Submission #39769

#	Time	Username	Problem	Language	Result	Execution time	Memory
39769		Sa1378	Split the sequence (APIO14_sequence)	C++14	60 / 100	2000 ms	91652 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define N ((ll)101*1000)
#define K ((ll)210)
#define INF ((ll)2e18)

int n,k,a[N],bst[K][N];
ll prt[N],dp[N],sum2;
vector <pair<pair<ll,ll>,int> > v;

ld barkhord(pair<ll,ll> x,pair<ll,ll> y){return (ld)(x.second-y.second)/(y.first-x.first);}

void add(ll a,ll b,int id)
{
	while(v.size()>1 && barkhord({a,b},v[(int)v.size()-2].first)<=barkhord(v.back().first,v[(int)v.size()-2].first))v.pop_back();
	v.push_back({{a,b},id});
}

pair <ll,ll> solve(ll x)
{
	int l=-1,r=(int)v.size()-1;
	while(l<r-1)
	{
		int mid=(l+r)/2;
		if(barkhord(v[mid].first,v[mid+1].first)>=x)r=mid;
		else l=mid;
	}
	return {v[r].first.first*x+v[r].first.second,v[r].second};
}

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i],prt[i]=(i?prt[i-1]:0)+a[i],dp[i]=prt[i]*prt[i],sum2+=a[i]*a[i];
	for(int _=0;_<k;_++)
	{
		v.clear();
		add(0,0,-1);
		for(int i=0;i<n;i++)
		{
			pair <ll,ll> ex;ex=solve(prt[i]);
		//	cout<<-prt[i]<<" "<<dp[i]+prt[i]*prt[i]<<"\n";
			add(-2*prt[i],dp[i]+prt[i]*prt[i],i);
			dp[i]=ex.first+prt[i]*prt[i];
			bst[_][i]=ex.second;
		}
	}
	cout<<(prt[n-1]*prt[n-1]-dp[n-1])/2<<"\n";
	int now=n-1;
	vector <ll> res;
	for(int i=k-1;i>=0;i--)
	{
		now=bst[i][now];
		res.push_back(now+1);
	}
	reverse(res.begin(),res.end());
	for(auto u:res)cout<<u<<" ";
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29