Submission #349154

#	Time	Username	Problem	Language	Result	Execution time	Memory
349154		aarr	Split the sequence (APIO14_sequence)	C++14	49 / 100	158 ms	131076 KiB

sequence

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

const int N = 100 * 1000 + 5, K = 205;
const long long inf = 1e18 + N;
int n, k;

int a[N];
long long dp[N][K];
long long ps[N];
int par[N][K];
vector <int> vec;

long long get(int lv, int x, int y) {
	return 1ll * (ps[x] - ps[y]) * (ps[x] - ps[y]) + dp[y][lv - 1];
}

void solve(int lv, int l, int r, int s, int e) {
	if (r <= l) {
		return;
	}
	int md = (l + r) / 2;
	for (int i = s; i <= e; i++) {
		if (get(lv, md, i) < dp[md][lv]) {
			par[md][lv] = i;
			dp[md][lv] = get(lv, md, i);
		}
	}
	solve(lv, l, md, s, par[md][lv]);
	solve(lv, md + 1, r, par[md][lv], e);
}

int main() {
	cin >> n >> k;
	k++;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		ps[i] = ps[i - 1] + a[i];
		for (int j = 0; j <= k; j++) {
			dp[i][j] = inf;
		}
	}
	for (int j = 1; j <= k; j++) {
		solve(j, 1, n + 1, 0, n);
	//	for (int i = 1; i <= n; i++) {
	//		cout << "73 " << i << " " << j << " " << dp[i][j] << endl;
	//	}
	}
	cout << (1ll * ps[n] * ps[n] - dp[n][k]) / 2 << '\n';
	int v = n;
	for (int j = k; j > 0; j--) {
		v = par[v][j];
		if (v) {
			vec.push_back(v);
		}
	}
	sort(vec.begin(), vec.end());
	for (auto x : vec) {
		cout << x << " ";
	}
	return 0;
}

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