Submission #155057

#	Time	Username	Problem	Language	Result	Execution time	Memory
155057		aer0park	Split the sequence (APIO14_sequence)	C++14	100 / 100	1817 ms	85496 KiB

sequence

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll cnt,sz,n,k,p[100006],dp[100002][5];
int sv[100002][202],st[100005],v[100006];
vector<int> anw;
 
double get(ll a,ll b,ll q)
{
	a=st[a],b=st[b];
	if(p[a]==p[b]) return -1e15;
	return (double)(p[b]*p[b]-p[a]*p[a]+dp[a][q%2]-dp[b][q%2])/(double)(p[b]-p[a]);
}
 
void push(ll x,ll d)
{
	st[sz]=x;
	while(sz>=2&&get(sz,sz-1,d)<get(sz-1,sz-2,d))
	{
		sz--,st[sz]=x;
	}
	sz++;
}
 
ll val(ll x,ll d)
{
	while(cnt<sz-1&&p[x]>=get(cnt,cnt+1,d)) cnt++;
	ll nw=st[cnt];
	sv[x][d+1]=nw;
	return p[x]*p[nw]-p[nw]*p[nw]+dp[nw][d%2];
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>v[i],p[i]=p[i-1]+(ll)v[i];
	for(int i=1;i<=k;i++)
	{
		cnt=0,sz=0;
		push(0,0);
		for(int j=1;j<=n;j++)
		{
			dp[j][i%2]=val(j,i-1);
			push(j,i-1);
		}
	}
	cout<<dp[n][k%2]<<"\n";
	ll g=n;
	for(int i=k;i>=1;i--)
	{
		g=sv[g][i];
		anw.push_back(g);
	}
	reverse(anw.begin(),anw.end());
	for(int i=0;i<k;i++)
		cout<<anw[i]<<" ";
	return 0;
}

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