Submission #98427

#	Time	Username	Problem	Language	Result	Execution time	Memory
98427		Anai	Split the sequence (APIO14_sequence)	C++14	100 / 100	1530 ms	82968 KiB

sequence

#include <bits/stdc++.h>
#define rev(v) (v.rbegin())
using namespace std;

using i64 = long long;
using f64 = double;

const int K = 201, N = 100005;


struct Line {
	i64 a, b;
	int idx;

	Line(i64 _a, i64 _b, int _idx) {
		a = _a, b = _b, idx = _idx; }

	Line() {
		a = 0, b = 1e18; }

	inline i64 operator () (const i64 &x) {
		return a * x + b; } };


int far[K][N];
vector<i64> dp[2];

deque<Line> dq;
vector<i64> v, s;
vector<int> ans;
int n, k;


static f64 intersect(const Line &l1, const Line &l2) {
	return (l1.b - l2.b) / (l2.a - l1.a); }


int main() {
#ifdef HOME
	freopen("sequences.in", "r", stdin);
	freopen("sequences.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	Line my_line;

	cin >> n >> k;
	dp[0].resize(n);
	v.resize(n);
	for (auto &i: v)
		cin >> i;

	s.resize(n);
	s[0] = v[0];
	for (int i = 1; i < n; ++i)
		s[i] = s[i - 1] + v[i];

	for (int i = 0; i < n; ++i)
		dp[0][i] = s[i] * (s.back() - s[i]);

	dp[1].resize(n);
	for (int it = 1; it < k; ++it) {
		dq.emplace_back(s[it - 1] + s.back(), dp[0][it - 1] - s.back() * s[it - 1], it - 1);

		for (int i = it; i < n; ++i) {
			while (dq.size() > 1 && dq[0](s[i]) <= dq[1](s[i]))
				dq.pop_front();

			dp[1][i] = dq[0](s[i]) - s[i] * s[i];
			far[it][i] = dq[0].idx;

			my_line = {s.back() + s[i], dp[0][i]- s.back() * s[i], i};
			while (dq.size() > 1 && (dq.back().a == my_line.a || intersect(rev(dq)[0], rev(dq)[1]) > intersect(rev(dq)[0], my_line)))
				dq.pop_back();
			dq.push_back(my_line); }

		dq.clear();
		swap(dp[0], dp[1]); }

	auto it = max_element(begin(dp[0]), end(dp[0]));

	cout << *it << '\n';
	ans.reserve(k);

	ans.push_back(it - begin(dp[0]));
	for (int i = k - 1; i > 0; --i)
		ans.push_back(far[i][ans.back()]);

	reverse(begin(ans), end(ans));
	for (auto i: ans)
		cout << i + 1 << ' ';
	cout << endl;

	return 0; }

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