Submission #1133496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133496		figgles	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ii = pair<int,int>;

signed main() {
	int n,splits;
	cin >> n >> splits;
	vector<vector<int>> dp(n, vector<int>(splits+2));
	vector<vector<int>> pos(n, vector<int>(splits+2));

	vector<int> xs(n);
	vector<int> prefix(n);
	for (int i = 0ll ; i < n; ++i) {
		cin >> xs[i];
		prefix[i] = prefix[max(i-1,0ll)] + xs[i];
	}

	for (int i = 0ll; i < n-1; ++i) {
		dp[i][1] = (prefix[n-1] - prefix[i]) * prefix[i];
	}

	for (int k = 2; k <= splits+1; ++k) {
		for (int i = 0ll; i < n; ++ i) {
			for (int l = 0ll; l < i; ++l) {
				int v = dp[l][k-1] + (prefix[i] - prefix[l])*(prefix[n-1]-prefix[i]);
				if (v >= dp[i][k]) {
					dp[i][k] = v;
					pos[i][k] = l;
				}
			}	
		}
	}
	cout << dp[n-1][splits+1] << '\n';

	int cur = n-1;
	vector<int> path;
	for (int k = splits; k >= 0ll; k--) {
		for (int l = cur-1; l >= 0ll; --l) {
			if (dp[l][k] + (prefix[cur] - prefix[l])*(prefix[n-1]-prefix[cur]) == dp[cur][k+1]) {
				path.push_back(l+1);
				cur = l;
				break;
			}
		}
	}
	for(int i = path.size()-1; i >= 0ll; --i) {
		cout << path[i] << ' ';
	}

	cout << '\n';
}

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