Submission #785788

#	Time	Username	Problem	Language	Result	Execution time	Memory
785788		acatmeowmeow	Split the sequence (APIO14_sequence)	C++11	71 / 100	76 ms	131072 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

//#define int long long 

const int N = 1e5, MAXK = 200;
int n, K, prefix[N + 5], par[N + 5][MAXK + 5];
long long dp[N + 5][MAXK + 5];

struct line {
	long long m, b;
   	int par;
	long long cross(line x) { return (x.b - b)/(m - x.m); }
	long long query(int pos) { return (long long)pos*m + b; }
};

deque<line> dq[MAXK + 5];

pair<long long, int> query(int pos, int layer) {
	while (dq[layer].size() >= 2) {
		line f = dq[layer].front(), se = dq[layer][1];
		if (f.query(pos) > se.query(pos)) break;
		else dq[layer].pop_front();
	}
	return { dq[layer].front().query(pos), dq[layer].front().par };
}

void add(line x, int layer) {
	while (dq[layer].size() >= 2) {
		line f = dq[layer].back(), se = dq[layer][dq[layer].size() - 2];
		if (f.m == x.m && f.b > x.b) return;
		else if (f.m == x.m && f.b <= x.b) dq[layer].pop_back();
		else if (x.cross(f) < x.cross(se)) dq[layer].pop_back();
		else break;
	}
	dq[layer].push_back(x);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> K;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		prefix[i] = prefix[i - 1] + x;
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= K; j++) {
			dp[i][j] = -1e9;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= min(K, i - 1); j++) {
			if (!j) { dp[i][0] = 0; continue; }
			pair<long long, int> res = query(prefix[i], j - 1);
			dp[i][j] = res.first, par[i][j] = res.second;
		}
		for (int j = 0; j <= min(K, i - 1); j++) {
			line x = {(long long)prefix[i], (long long)-prefix[i]*prefix[i] + dp[i][j], i};
			add(x, j);
		}
	}
	cout << dp[n][K] << '\n';
	int index = n, layer = K;
	while (true) {
		if (!par[index][layer]) break;
		else cout << par[index][layer] << " ";
		index = par[index][layer], layer--;
	}
	cout << '\n';
	return 0;
}

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