Submission #582937

#	Time	Username	Problem	Language	Result	Execution time	Memory
582937		1ne	Split the sequence (APIO14_sequence)	C++14	50 / 100	2090 ms	47948 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long score = -1,cur = -1,prev = -1;
};
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];
	}
	vector<vector<node>>dp(n + 1,vector<node>(k + 1));
	auto getscore = [&](int l,int r){
		return pref[r] - pref[l];
	};
	for (int i = 0;i<n;++i){
		dp[i][0] = {0,i,-1};
	}
	for (int i = 1;i<n;++i){
		for (int j = 1;j<=k;++j){
			for (int p = 0;p < i;++p){
				if (j > 1 && p == 0)continue;
				if (dp[p][j - 1].cur == -1)continue;
				if (dp[i][j].score < dp[p][j - 1].score + getscore(dp[p][j - 1].cur,i) * getscore(i,n)){
					dp[i][j] = {dp[p][j - 1].score + getscore(dp[p][j - 1].cur,i) * getscore(i,n),i,p};
				}
			}
		}
	}
	node ans;
	for (int i = 1;i<n;++i){
			if (dp[i][k].score > ans.score && dp[i][k].cur==i){
				ans = dp[i][k];
			}
	}
	vector<int>ind;
	int p = k - 1;
	cout<<ans.score<<'\n';
	for (int i = 0;i<k;++i){
		ind.push_back(ans.cur);
		if (i!=k - 1){
			ans = dp[ans.prev][p];
			--p;
		}
	}
	reverse(ind.begin(),ind.end());
	for (auto x:ind)cout<<x<<" ";
	cout<<'\n';
	return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

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