Submission #402516

#	Time	Username	Problem	Language	Result	Execution time	Memory
402516		BERNARB01	Split the sequence (APIO14_sequence)	C++17	0 / 100	424 ms	22788 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const long long is_query = -(1LL<<62);

struct line {
	long long m, b;
	int id;
	mutable function<const line*()> succ;
	bool operator<(const line& rhs) const {
		if (rhs.b != is_query) return m < rhs.m;
		const line* s = succ();
		if (!s) return 0;
		long long x = rhs.m;
		return b - s->b < (s->m - m) * x;
	}
};

struct dynamic_hull : public multiset<line> {
	const long long inf = LLONG_MAX;
	bool bad(iterator y) {
		auto z = next(y);
		if (y == begin()) {
			if (z == end()) return 0;
			return y->m == z->m && y->b <= z->b;
		}
		auto x = prev(y);
		if (z == end()) return y->m == x->m && y->b <= x->b;
		long long v1 = (x->b - y->b);
		if (y->m == x->m) v1 = x->b > y->b ? inf : -inf;
		else v1 /= (y->m - x->m);
		long long v2 = (y->b - z->b);
		if (z->m == y->m) v2 = y->b > z->b ? inf : -inf;
		else v2 /= (z->m - y->m);
		return v1 >= v2;
	}
	void insert_line(long long m, long long b, int id) {
		auto y = insert({ m, b, id });
		y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
		if (bad(y)) { erase(y); return; }
		while (next(y) != end() && bad(next(y))) erase(next(y));
		while (y != begin() && bad(prev(y))) erase(prev(y));
	}
	pair<long long, int> eval(long long x) {
		auto l = *lower_bound((line) { x, is_query });
		return pair<long long, int>(l.m * x + l.b, l.id);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<long long> sr(n);
	sr[n - 1] = a[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		sr[i] = sr[i + 1] + a[i];
	}
	vector<vector<pair<long long, int>>> dp(k + 1, vector<pair<long long, int>>(n, {0, -1}));
	//for (int i = 0; i < n; i++) {
		//dp[0][i] = {sr[i] * (sr[n - 1] - sr[i]), -1};
	//}
	for (int i = 1; i <= k; i++) {
		dynamic_hull chL, chR;
		chL.insert_line(sr[0], dp[i - 1][0].first, 0);
		for (int j = 1; j < n; j++) {
			pair<long long, int> tmp = chL.eval(sr[j]);
			dp[i][j] = max(dp[i][j], {tmp.first - sr[j] * sr[j], tmp.second});
			chL.insert_line(sr[j], dp[i - 1][j].first, j);
		}
		chR.insert_line(sr[n - 1], dp[i - 1][n - 1].first, n - 1);
		for (int j = n - 2; j >= 0; j--) {
			pair<long long, int> tmp = chR.eval(sr[j]);
			dp[i][j] = max(dp[i][j], {tmp.first - sr[j] * sr[j], tmp.second});
			chR.insert_line(sr[j], dp[i - 1][j].first, j);
		}
	}
	pair<long long, int> ans = *max_element(dp[k].begin(), dp[k].end());
	cout << ans.first << '\n';
	vector<int> res;
	int ptr = ans.second;
	while (k >= 1) {
		res.push_back(dp[k][ptr].second);
		ptr = dp[k][ptr].second;
		k--;
	}
	reverse(res.begin(), res.end());
	for (const auto& x : res) {
		cout << x + 1 << " ";
	}
	cout << '\n';
	return 0;
}

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