Submission #337224

#	Time	Username	Problem	Language	Result	Execution time	Memory
337224		penguinhacker	Split the sequence (APIO14_sequence)	C++14	0 / 100	70 ms	131076 KiB

sequence

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

#define ll long long
#define ar array

const int mxN = 100001;
int n, k, a[mxN];
ll pre[mxN];
ll dp[mxN][201];
int last[mxN][201];

struct Line {
	ll m, b, ind;
	ll eval(ll x) {return m * x + b;}
};
double isect(Line& a, Line& b) {
	return (double)(a.b - b.b) / (b.m - a.m);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	for (int i = 1; i <= n; ++i) {
		dp[i][1] = pre[i] * (pre[n] - pre[i]);
	}
	for (int rep = 2; rep <= k; ++rep) {
		deque<Line> dq;
		for (int i = rep; i < n; ++i) {
			Line cur = {pre[i - 1], dp[i - 1][rep - 1] - pre[n] * pre[i - 1], i - 1};
			while(dq.size() >= 2 && isect(cur, dq[dq.size() - 2]) < isect(dq.back(), dq[dq.size() - 2]))
				dq.pop_back();
			dq.push_back(cur);
			while(dq.size() >= 2 && dq[1].eval(pre[i]) > dq[0].eval(pre[i]))
				dq.pop_front();
			dp[i][rep] = pre[i] * (pre[n] - pre[i]) + dq[0].eval(pre[i]);
			last[i][rep] = dq[0].ind;
		}
	}
	int ind = -1;
	for (int i = k; i < n; ++i) {
		if (ind == -1 || dp[i][k] > dp[ind][k]) {
			ind = i;
		}
	}
	cout << dp[ind][k] << "\n";
	for (int i = k; i >= 1; --i) {
		cout << ind << " ";
		ind = last[ind][i];
	}
	return 0;
}
// notes
// dp[i] = dp[j] + (pre[i] - pre[j]) * (pre[n] - pre[i]);
// dp[i] = pre[i] * (pre[n] - pre[i]) + max(pre[j] * pre[i] + dp[j] - pre[n] * pre[j])

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