제출 #785776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785776		acatmeowmeow	수열 (APIO14_sequence)	C++11	60 / 100	86 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], dp[N + 5][MAXK + 5], par[N + 5][MAXK + 5];

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

deque<line> dq[MAXK + 5];

pair<int, 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] = -1e18;
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[i][0] = 0;
		line x = {prefix[i], -prefix[i]*prefix[i] + dp[i][0], i};
		add(x, 0);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= min(K, i - 1); j++) {
			pair<int, int> res = query(prefix[i], j - 1);
			dp[i][j] = res.first, par[i][j] = res.second;
			//line x = {prefix[i], -prefix[i]*prefix[i] + dp[i][j], i};
			//add(x, j);
			/*for (int k = 1; k < i; k++) {
				int cur = dp[k][j - 1] + (prefix[i] - prefix[k])*prefix[k];
				if (dp[i][j] < cur) dp[i][j] = cur, par[i][j] = k;
			}*/
		}
		for (int j = 1; j <= min(K, i - 1); j++) {
			line x = {prefix[i], -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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29