Submission #670115

#	Time	Username	Problem	Language	Result	Execution time	Memory
670115		Radin_Zahedi2	Split the sequence (APIO14_sequence)	C++17	0 / 100	65 ms	2660 KiB

sequence

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
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 opt[N][K];
ll dp[N];
ll dp2[N];


int l = 1, r = 0;
int sum = 0;
ll cost = 0;

void add(int s) {
	if (s == 0) {
		l--;

		cost += arr[l] * arr[l];
		cost += 1ll * arr[l] * sum;
		cost += 1ll * sum * arr[l];

		sum += arr[l];
	}
	else {
		r++;

		cost += arr[r] * arr[r];
		cost += 1ll * arr[r] * sum;
		cost += 1ll * sum * arr[r];

		sum += arr[r];
	}
}

void rem(int s) {
	if (s == 0) {
		sum -= arr[l];

		cost -= arr[l] * arr[l];
		cost -= 1ll * arr[l] * sum;
		cost -= 1ll * sum * arr[l];

		l++;
	}
	else {
		sum -= arr[r];

		cost -= arr[r] * arr[r];
		cost -= 1ll * arr[r] * sum;
		cost -= 1ll * sum * arr[r];

		r--;
	}
}

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

	int m = (l + r) / 2;
	
	for (int i = l; i <= m; i++) {
		add(1);
	}

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

		rem(0);
	}


	for (int i = min(m, optr); i >= opt[m]; i--) {
		add(0);
	}
	divide(m + 1, r, opt[m], optr, opt);

	for (int i = opt[m] - 1; i >= optl; i--) {
		add(0);
	}
	for (int i = m; i >= l; i--) {
		rem(1);
	}
	divide(l, m - 1, optl, opt[m], opt);
}

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

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

		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];
	}
}

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; i >= 1; i--) {
		have.push(opt[i][now]);
		now = opt[i][now];
	}

	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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29