제출 #34886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34886		cheater2k	수열 (APIO14_sequence)	C++14	33 / 100	2000 ms	84600 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, K = 205;
const long long inf = 1e18;

int n, k;
long long a[N];
long long f[N][2];
int trace[N][K];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k; ++k;
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] += a[i-1];

	for (int i = 0; i <= n; ++i) f[i][0] = inf;

	f[0][0] = 0;
	for (int j = 1; j <= k; ++j) {
		for (int i = 0; i <= n; ++i) f[i][j & 1] = inf;

		int pt = 0;
		for (int i = 1; i <= n; ++i) {
			while(pt < i - 1) {
				long long cur = f[pt][1 - (j&1)] + (a[i] - a[pt]) * (a[i] - a[pt]);
				long long nxt = f[pt + 1][1 - (j&1)] + (a[i] - a[pt + 1]) * (a[i] - a[pt + 1]);
				if (cur >= nxt) ++pt; else break;
			}
			f[i][j & 1] = min(f[i][j & 1], f[pt][1 - (j&1)] + (a[i] - a[pt]) * (a[i] - a[pt]));
			trace[i][j] = pt;
		}
	}

	long long ans = f[n][k & 1];
	ans = (a[n] * a[n] - ans) / 2;
	printf("%lld\n", ans);

	vector<int> vec;
	while(n) {
		n = trace[n][k--];
		vec.push_back(n);
	}
	vec.pop_back();
	for (int i = vec.size()-1; i >= 0; --i) printf("%d ", vec[i]); printf("\n");
}

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