Submission #23392

#	Time	Username	Problem	Language	Result	Execution time	Memory
23392		petrpan	Split the sequence (APIO14_sequence)	C++14	50 / 100	2000 ms	36428 KiB

sequence

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long n,a[100010],f[210][10010],b[100010],num,k,trace[210][10010];
vector<int> p;
/*
struct ioi2
{
	long long a,b;
}it[210][400010];

long long get(ioi2 p ,long long x)
{
	return (p.a*x+p.b);
}

void update(int tr,int p,int l,int r,ioi2 x)
{
	ioi2 y=it[tr][p];
	if (r<l) return;
	int m=(l+r)/2;
	if (get(x,b[l])>=get(y,b[l]) and get(x,b[r])>=get(y,b[r]))
	{
		it[tr][p]=x;
		return;
	}
	if (get(x,b[l])<=get(y,b[l]) and get(x,b[r])<=get(y,b[r]))
		return;
	if (get(x,b[m])>=get(y,b[m]) and get(x,b[l])>=get(y,b[l]))
	{
		update(tr,p*2+1,m+1,r,it[tr][p]);
		it[tr][p]=x;
		return;
	}
	if (get(x,b[m])<=get(y,b[m]) and get(x,b[l])<=get(y,b[l]))
	{
		update(tr,p*2+1,m+1,r,x);
		return;
	}
	if (get(x,b[m+1])>=get(y,b[m+1]) and get(x,b[r])>=get(y,b[r]))
	{
		update(tr,p*2,l,m,it[tr][p]);
		it[tr][p]=x;
		return;
	}
	if (get(x,b[m+1])<=get(y,b[m+1]) and get(x,b[r])<=get(y,b[r]))
	{
		update(tr,p*2,l,m,x);
		return;
	}
}	

long long query(int tr,int p,int l,int r,int x)
{
	if (x<l or x>r) return 0;
	if (l==r) return get(it[tr][p],b[x]);
	long long res=get(it[tr][p],b[x]);
	return res=max(res,max(query(tr,p*2,l,(l+r)/2,x),query(tr,p*2+1,(l+r)/2+1,r,x)));
}*/

int main()
{	
	cin >> n >> k;
	for (int i=1;i<=n;i++)
		cin >> a[i],a[i]+=a[i-1],b[i]=a[i];
	sort(b+1,b+n+1);
	num=unique(b+1,b+n+1)-b-1;
	/*
	for (int i=1;i<=k+1;i++)
		for (int j=1;j<=n;j++)
	{
		if (i==1) f[i][j]=0;
		else
		{
			ioi2 tp;
			tp.a=-a[j];
			tp.b=f[i-1][j]-a[j]*a[j];
			int pos=lower_bound(b+1,b+num+1,a[j])-b;
			update(i-1,1,1,num,tp);
			f[i][j]=query(i-1,1,1,num,pos);
		}
	}*/
	for (int i=1;i<=n;i++)
		f[0][i]=-1e18;
	for (int i=1;i<=k+1;i++)
		for (int j=0;j<=n;j++)
		{
			for (int k=1;k<j;k++)
			{
				f[i][j]=max(f[i][j],f[i-1][k]+(a[j]-a[k])*a[k]);
				if (f[i][j]==f[i-1][k]+(a[j]-a[k])*a[k]) trace[i][j]=k;
			}
		}
	cout << f[k+1][n] << "\n";
	int t1=k+1,t2=n;
	while (t1)
	{
		p.push_back(trace[t1][t2]);
		t2=trace[t1][t2];
		t1--;
	}
	while (p.size())
	{
		if (p.back()) cout << p.back() << " ";
		p.pop_back();
	}
}

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