Submission #1054798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054798		1ne	Split the sequence (APIO14_sequence)	C++14	50 / 100	2039 ms	110968 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<vector<long long>>>dp(n + 1,vector<vector<long long>>(k + 1,vector<long long>(2,-1)));
	for (int i = 0;i<n;++i){
		dp[i][0][0] = 0;
		dp[i][0][1] = -1;
	}
	for (int i = 1;i<=k;++i){
		for (int j = 1;j<n;++j){
			for (int p = 0;p<j;++p){
				if (dp[j][i][0] < dp[p][i - 1][0] + query(p,j - 1) * query(j,n - 1)){
					dp[j][i][0] = dp[p][i - 1][0] + query(p,j - 1) * query(j,n - 1);
					dp[j][i][1] = p;
				}
			}
		}
	}
	long long ans = -1;
	int v = -1;
	for (int i = 1;i<n;++i){
		if (dp[i][k][0] > ans){
			ans = dp[i][k][0];
			v = i;
		}
	}
	cout<<ans<<'\n';
	vector<int>pos;
	for (int i = 0;i<k;++i){
		pos.push_back(v);
		v = dp[v][k - i][1];
	}
	reverse(pos.begin(),pos.end());
	for (auto x:pos)cout<<x<<" ";
	cout<<'\n';
	return 0;
}

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