Submission #43612

#	Time	Username	Problem	Language	Result	Execution time	Memory
43612		faustaadp	Split the sequence (APIO14_sequence)	C++14	100 / 100	652 ms	85016 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//#define getchar() getchar_unlocked()
using namespace std;
ll n,k,i,a[101010],p[101010],M,C,opt,j,vs;
ll d[2][100010],te,seb;
int op[201][100010],poi;
int v[202];
pair<pair<ll,ll> ,int>  vt[101010];
pair<pair<ll,ll> ,int> L1,L2,L3;
bool bo;
void bt(ll aa,ll bb)
{
	ll ii,h=0;
	for(ii=0;ii<k;ii++)
	{
		v[h]=op[aa][bb];
		h++;
		bb=op[aa][bb]+1;
		aa--;
	}
}
inline void fs(ll& p) {
	static char c;
   	while ((c = getchar()) < '0');
	for (p = c-'0'; (c = getchar()) >= '0'; p = p*10+c-'0');
}
int main()
{
//	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//cin>>n>>k;
	fs(n);
	fs(k);
	for(i=1;i<=n;i++)
	{
		fs(a[i]);
//		cin>>a[i];
		p[i]=p[i-1]+a[i];
	}
	pair<pair<ll,ll>,ll> aa;
	ll ava;
	for(i=1;i<=k;i++)
	{
	//	vt.clear();
	//	vt.reserve(n);
		poi=0;
		vs=0;
		te=0;
		seb=0;
		for(j=n-1;j>=1;j--)
		{
			M=p[j];
			C=p[j]*p[n]-p[j]*p[j]+d[(i-1)&1][j+1];
			aa=mp(mp(M,C),j);
			bo=0;
			while(vs>=2)
			{
				L1=vt[vs-1];
				L2=vt[vs-2];
				L3=aa;
				if((L2.fi.se-L1.fi.se)*(L2.fi.fi-L3.fi.fi)<(L3.fi.se-L2.fi.se)*(L1.fi.fi-L2.fi.fi))
					break;
				if(!bo&&L2.se>seb){te--;bo=1;}
				poi--;
				//vt.pop_back();
				vs--;
			}
			vt[poi]=aa;
			poi++;
			//vt.push_back(aa);
			vs++;
			ava=p[j-1];
			while(te<vs-1)
			{
				L1=vt[te];
				L2=vt[te+1];
				if((L2.fi.se-L1.fi.se)>=(L1.fi.fi-L2.fi.fi)*ava)
					te++;
				else
					break;
			}
			//te--;
			seb=vt[te].se;
			opt=te;
			op[i][j]=vt[opt].se;
			d[i&1][j]=(vt[opt].fi.fi*p[j-1]+vt[opt].fi.se-p[j-1]*p[n]);
		}
	}
	cout<<d[k%2][1]<<"\n";
	bt(k,1);
	for(i=0;i<k;i++)
		if(i==k-1)
			cout<<v[i]<<"\n";
		else
			cout<<v[i]<<" ";
}

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