Submission #400226

#	Time	Username	Problem	Language	Result	Execution time	Memory
400226		l3nl3	Split the sequence (APIO14_sequence)	C++17	0 / 100	2083 ms	131076 KiB

sequence

// meowa

#include <bits/stdc++.h>

#define show(x) cerr << #x << "-> " << x << '\n';
#define ll long long
#define all(a) a.begin(), a.end()

using namespace std;

const int mxsz = 1e5+7;
const int inf = 1e9+1e2;
const int mod = 1e9+7;

int n, k, a[mxsz], s[mxsz], dp[mxsz][202], ans;
map <pair<int, int>, pair<int, int>> pr;

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n; i >= 1; i--) {
		s[i] = s[i+1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i][1] = (s[1] - s[i+1]) * s[i+1];
		pr[{i, 1}] = {i, 1}; 
		for (int lv = 2; lv <= i; lv++) {
			for (int j = 1; j < i; j++) {
				if (dp[i][lv] < dp[j][lv-1] + (s[j+1] - s[i+1]) * s[i+1]) {
					dp[i][lv] = dp[j][lv-1] + (s[j+1] - s[i+1]) * s[i+1];
					pr[{i, lv}] = {j, lv-1}; 
				}
			}
		}
	}
	ans = 1;
	for (int i = 2; i <= n; i++) {
		if (dp[i][k] > dp[ans][k]) {
			ans = i;
		}		
	}
	cout << dp[ans][k] << '\n';
	vector<int> an;
	pair<int, int> lt = {ans, k};
	while (lt.second != 1) {
		an.push_back(lt.first);
		lt = pr[lt];
	}
	an.push_back(lt.first);
	reverse(all(an));
	for (int x : an) cout << x << ' ';
}  

/*
7 3
4 1 3 4 0 2 3
*/

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