Submission #1133489

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

sequence

#include <bits/stdc++.h>

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

int 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 = 0 ; i < n; ++i) {
		cin >> xs[i];
		prefix[i] = prefix[max(i-1,0)] + xs[i];
	}

	for (int i = 0; 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 = 0; i < n; ++ i) {
			for (int l = 0; 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 i = n-1;
	int k = splits+1;
	vector<int> bt;
	while(k > 1) {
		bt.push_back(i);
		i = pos[i][k];
		k--;
	}
	for (int j = bt.size()-1; j >= 0; --j) {
		cout << bt[j]-1 << ' ';
	}
	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