Submission #1211159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211159		k1r1t0	Split the sequence (APIO14_sequence)	C++20	100 / 100	496 ms	81952 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 110000;
const int K = 210;

struct pt {ll x, y;};
pt operator +(pt a, pt b) {return {a.x + b.x, a.y + b.y};}
pt operator -(pt a, pt b) {return {a.x - b.x, a.y - b.y};}
ll cross(pt a, pt b) {return a.x * b.y - a.y * b.x;}
ll cross(pt a, pt b, pt c) {return cross(b - a, c - b);}
ll get(pt a, ll x) {return a.x * x + a.y;}

int n, k, p[K][N];
ll a[N], dp[N];

deque<pair<pt, int>> cht;

void init() {
	cht.clear();
}

void upd(ll k, ll b, int t) {
	pt cur = {k, b};
	while (cht.size() > 1 && cross(end(cht)[-2].first, cht.back().first, cur) >= 0)
		cht.pop_back();
	cht.push_back({cur, t});
}

pair<ll, int> get(ll x) {
	assert(!cht.empty());
	while (cht.size() > 1 && get(cht[0].first, x) <= get(cht[1].first, x))
		cht.pop_front();
	return {get(cht[0].first, x), cht[0].second};
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k; k++;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		a[i] += a[i - 1];
	for (int t = 2; t <= k; t++) {
		init();
		for (int i = t - 1; i <= n; i++) {
			ll old = dp[i];
			if (i >= t)
				tie(dp[i], p[t][i]) = get(a[i]);
			upd(a[i], old - a[i] * a[i], i);
		}
	}
	vector<int> ans;
	int t = n;
	do {
		t = p[k][t];
		k--;
		ans.push_back(t);
	} while (t != 0);
	ans.pop_back();
	reverse(begin(ans), end(ans));
	cout << dp[n] << '\n';
	for (int x : ans)
		cout << x << ' ';
}

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