Submission #1039689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039689		TrungDuy3107	Split the sequence (APIO14_sequence)	C++14	33 / 100	341 ms	1624 KiB

sequence

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

#define maxn 207
typedef long long LL;

long long dp[maxn][maxn];
int trace[maxn][maxn];
int arr[maxn];
long long prefix[maxn];

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	int n, k;long long sum = 0;
	cin >> n >> k;k++;
	for(int i=1;i<=n;i++) {
		cin >> arr[i], sum += arr[i];
		prefix[i] = prefix[i-1] + arr[i];
	}

	for(int i=1;i<=n;i++) dp[0][i] = -1;

	for(int lev=1;lev<=k;lev++) {
		for(int i=1;i<=n;i++) {
			dp[lev][i] = 0;
			pair<long long, int> best = {0,-1};
			for(int j=1;j<=i;j++) if(dp[lev][j-1] != -1) {
				best = max(best, {dp[lev-1][j-1] + (prefix[i] - prefix[j-1]) * (sum - prefix[i]), j});
			}
			dp[lev][i] = best.first;
			trace[lev][i] = best.second;
		}
	}

	cout << dp[k][n] << '\n';
	int cur = n;
	vector<int> res;
	while(cur > 0 && k > 0) {
		res.push_back(trace[k][cur]-1);
		cur = trace[k][cur] - 1;
		k--;
	}

	reverse(res.begin(),res.end());
	for(int i=1;i<res.size();i++) cout << res[i] << ' ';

	return 0;
}

Compilation message (stderr)

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

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