Submission #975512

#	Time	Username	Problem	Language	Result	Execution time	Memory
975512		Nexus	Split the sequence (APIO14_sequence)	C++17	50 / 100	2023 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N=1e5+9,M=2e18+9,mod=1e9+7;

ll a[N],s[N],dp[N][209],p[N][209],n,k,x,y,z,o=-M;
vector<ll>v;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n>>k;
	for(ll i=1;i<=n;++i)cin>>a[i];
	
	for(ll i=n;i;--i)s[i]=a[i]+s[i+1];
	
	for(ll i=1;i<n;++i)
	{
		dp[i][1]=(s[1]-s[i+1])*s[i+1],p[i][1]=i;
		if(dp[i][1]>o)o=dp[i][1],z=i;
	}
	
	for(ll j=2;j<=k;++j)
	{
		for(ll i=j;i<=n;++i)
		{
			x=dp[j-1][j-1]+(a[j])*s[i+1],y=j-1;
			for(ll g=j-1;g<i;++g)
			{
				if(dp[g][j-1]+(s[g+1]-s[i+1])*s[i+1]>x)
				x=dp[g][j-1]+(s[g+1]-s[i+1])*s[i+1],y=g;
			}
			dp[i][j]=x,p[i][j]=y;
			if(j==k && x>o)o=x,z=i;
		}
	}
	
	/*
	for(ll i=1;i<=n;++i)
	{
		for(ll j=1;j<=k;++j)
		cout<<dp[i][j]<<' ';
		cout<<'\n';
	}
	*/
	
	cout<<dp[z][k]<<'\n';
	
	x=z;
	for(ll i=k;i;--i)
	{
		v.push_back(x);
		x=p[x][i];
	}
	
	reverse(v.begin(),v.end());
	for(auto i:v)cout<<i<<' ';
	
}

/*
7 3
4 1 3 4 0 2 3

108
1 3 5
*/

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