Submission #43599

#	Time	Username	Problem	Language	Result	Execution time	Memory
43599		faustaadp	Split the sequence (APIO14_sequence)	C++14	54 / 100	2059 ms	85336 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,k,i,a[101010],p[101010],M,C,opt,j,vs;
ll d[101010][2],te,seb;
int op[101010][202];
vector<ll> v;
vector<pair<pair<ll,ll> ,int> > vt;
pair<pair<ll,ll> ,int> L1,L2,L3;
bool bo;
void bt(ll aa,ll bb)
{
	if(bb==0)
		return ;
	v.pb(op[aa][bb]);
	bt(op[aa][bb]+1,bb-1);
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		p[i]=p[i-1]+a[i];
	}
	for(i=1;i<=k;i++)
	{
		vt.clear();
		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[j+1][(i-1)%2];
			pair<pair<ll,ll>,ll> 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;}
				vt.pop_back();
				vs--;
			}
			vt.push_back(aa);
			vs++;
			ll 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[j][i]=vt[opt].se;
			d[j][i%2]=(vt[opt].fi.fi*p[j-1]+vt[opt].fi.se-p[j-1]*p[n]);
		}
	}
	cout<<d[1][k%2]<<"\n";
	bt(1,k);
	for(i=0;i<v.size();i++)
		if(i==v.size()-1)
			cout<<v[i]<<"\n";
		else
			cout<<v[i]<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v.size();i++)
           ^
sequence.cpp:76:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i==v.size()-1)
       ^

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