Submission #1054163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054163		1ne	Split the sequence (APIO14_sequence)	C++14	0 / 100	1760 ms	131072 KiB

sequence

/*
*  author : Apiram                  
*  created: 26.06.2023 00:43:43
*/

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,k;cin>>n>>k;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>pref(n + 1,0);
	for (int i = 0;i<n;++i){
	 pref[i + 1] = pref[i] + arr[i];
	}
	auto query = [&](int u,int v){
	  return pref[v + 1] - pref[u];
	};
	vector<vector<pair<int,int>>>child(n,vector<pair<int,int>>(n));;
	vector<vector<vector<long long>>>dp(n,vector<vector<long long>>(n,vector<long long>(k,-1)));
	function<long long(int,int,int)>solve = [&](int u,int v,int p){
	  if (p == k){
	  	return 0LL;
	  }
	  if (dp[u][v][p] != -1){
	  	return dp[u][v][p];
	  }
	  long long ans = -1;
	  long long p1 = 0,p2 = 0;
	  for (int i = u;i<=v;++i){
	  	if (i + 1 < v)
	  		p1 = (solve(i + 1,v,p + 1) + query(u,i) * query(i + 1,v));	
	  	if (i + 1 < v){
	  		p2 = (solve(u,i,p + 1) + query(u,i) * query(i + 1,v));
	  	}
	  	if (max(p1,p2) > ans){
	  		ans = max(p1,p2);
	  		child[u][v] = {i,0};
	  		if (p2 > p1){
	  			child[u][v] = {i,1};
	  		}
	  	}
	  }
	  return dp[u][v][p] = ans;
	};
	vector<int>pos;  	
	int l = 0,r = n - 1;
	cout<<solve(0,n - 1,0)<<'\n';
	for (int i = 0;i<k;++i){
		pos.push_back(child[l][r].first);
		if (child[l][r].second == 0){
			l = child[l][r].first;	
		}
	  	else{
	  		r = child[l][r].first;
	  	}
	}
	for (auto x:pos)cout<<x + 1<<" ";
	cout<<'\n';
	return 0;
}

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