Submission #670139

#	Time	Username	Problem	Language	Result	Execution time	Memory
670139		Radin_Zahedi2	Split the sequence (APIO14_sequence)	C++17	100 / 100	1408 ms	82124 KiB

sequence

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 2e18 + 5;


int n, k;
const int N = 1e5 + 5;
const int K = 2e2 + 5;
int arr[N];
int sum[N];
ll dist[N];

int opt[K][N];
ll dp[N];
ll dp2[N];


ll calc(int l, int r) {
	ll between = 1ll * sum[l - 1] * (sum[r] - sum[l - 1]);
	ll ans = dist[r] - dist[l - 1] - 2 * between;
	return ans;
}

void divide(int l, int r, int optl, int optr, int opt[]) {
	if (r < l) {
		return;
	}

	int m = (l + r) / 2;
	
	opt[m] = optl;
	dp2[m] = linf;
	for (int i = optl; i <= min(m, optr); i++) {
		if (dp[i - 1] + calc(i, m) < dp2[m]) {
			dp2[m] = dp[i - 1] + calc(i, m);
			opt[m] = i;
		}
	}

	divide(m + 1, r, opt[m], optr, opt);
	divide(l, m - 1, optl, opt[m], opt);
}

void dpdivide() {
	fill(dp + 0, dp + n + 1, linf);
	dp[0] = 0;

	for (int j = 1; j <= k + 1; j++) {
		divide(1, n, 1, n, opt[j]);

		for (int i = 1; i <= n; i++) {
			dp[i] = dp2[i];
		}

		dp[0] = linf;
	}
}

void init() {
}

void input() {
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		//arr[i] = 10000;
	}

	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + arr[i];
		
		dist[i] = dist[i - 1];
		dist[i] += arr[i] * arr[i];
		dist[i] += 2ll * arr[i] * sum[i - 1];
	}
}

void solve() {
	dpdivide();

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

	cout << ans / 2 << endl;


	stack<int> have;
	int now = n;
	for (int i = k + 1; i >= 2; i--) {
		have.push(opt[i][now] - 1);
		now = opt[i][now] - 1;
	}

	while (!have.empty()) {
		cout << have.top() << ' ';
		have.pop();
	}
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

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