Submission #337385

#	Time	Username	Problem	Language	Result	Execution time	Memory
337385		ogibogi2004	Split the sequence (APIO14_sequence)	C++14	22 / 100	288 ms	35436 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define move dafds
#define ll long long
const ll INF=2e15;
const ll MAXN=128,MAXK=128;
ll dp[MAXN][MAXN][MAXK];
pair<ll,ll> move[MAXN][MAXN][MAXK];
ll a[MAXN];
ll pref[MAXN];
ll n;
vector<ll>v;
ll solve(ll l,ll r,ll k)
{
	if(k==0)return 0;
	if(dp[l][r][k]!=-1)return dp[l][r][k];
	for(ll i=l;i<r;i++)
	{
		for(int j=0;j<k;j++)
		{
			ll val=(pref[i]-pref[l-1])*(pref[r]-pref[i])+solve(l,i,j)+solve(i+1,r,k-1-j);
			if(val>dp[l][r][k])
			{
				dp[l][r][k]=val;
				move[l][r][k]={i,j};
			}
		}
	}
	return dp[l][r][k];
}
void find_splits(ll l,ll r,ll k)
{
	if(k==0)return;
	v.push_back(move[l][r][k].first);
	find_splits(l,move[l][r][k].first,move[l][r][k].second);
	find_splits(move[l][r][k].first+1,r,k-1-move[l][r][k].second);
}
int main()
{
	ll k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		pref[i]=pref[i-1]+a[i];
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(1,n,k)<<endl;
	find_splits(1,n,k);
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
	cout<<endl;
return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<v.size();i++)cout<<v[i]<<" ";
      |              ~^~~~~~~~~

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