Submission #361834

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

sequence

// source: https://oj.uz/problem/view/APIO14_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];
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];
	}
	vector<ll> dp(n + 1);
	vector<ll> dpn(n + 1);
	for (int i = 1; i <= n; ++i) {
		dp[i] = 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] - pre[n] * pre[i - 1], i - 1};
			while(dq.size() >= 2 && isect(cur, dq.end()[-2]) < isect(dq.back(), dq.end()[-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();
			dpn[i] = pre[i] * (pre[n] - pre[i]) + dq[0].eval(pre[i]);
			last[i][rep] = dq[0].ind;
		}
		swap(dp, dpn);
	}
	int ind = max_element(dp.begin(), dp.end()) - dp.begin();
	cout << dp[ind] << "\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