Submission #28734

#	Time	Username	Problem	Language	Result	Execution time	Memory
28734		szawinis	Split the sequence (APIO14_sequence)	C++14	78 / 100	693 ms	87296 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1e5)+1, K = 201;

struct MaxHull {
	struct line {
		ll m, c;
		int i;
		ll getVal(ll x) { return m*x + c; };
	};
	int idx = 0;
	vector<line> lines;
	bool bad(line l1, line l2, line l3) {
		assert(l1.m <= l2.m && l2.m <= l3.m);
		return (double) (l3.c-l1.c)*(l1.m-l2.m) <= (double) (l2.c-l1.c)*(l1.m-l3.m);
	}
	void update(ll m, ll c, int i) {
		line l = {m, c, i};
		while(lines.size() > 3 && bad(lines[lines.size()-2], lines[lines.size()-1], l)) lines.pop_back();
		lines.push_back(l);
	}
	pair<ll, int> query(ll x) {
		assert(!lines.empty());
		while(idx+1 < lines.size() && lines[idx+1].getVal(x) >= lines[idx].getVal(x)) ++idx;
		return make_pair(lines[idx].getVal(x), lines[idx].i);
	}
} hull;

int n, k, a[N], trace[K][N];
ll ans, s[N], dp[N];
vector<int> order;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i-1] + a[i];
		hull.update(s[i], -s[i]*s[i], i);
	}
	for(int cnt = 1; cnt <= k; cnt++) {
		memset(dp, 0, sizeof(dp));
		for(int i = cnt+1; i <= n; i++) tie(dp[i], trace[cnt][i]) = hull.query(s[i]);
		hull.idx = 0;
		hull.lines.clear();
		for(int i = cnt+1; i <= n; i++) hull.update(s[i], dp[i] - s[i]*s[i], i);
	}
	for(int cnt = k, i = n; cnt >= 1; i = trace[cnt][i], cnt--) order.push_back(trace[cnt][i]);
	reverse(order.begin(), order.end());
	cout << dp[n] << endl;
	for(int i: order) cout << i << ' ';
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, int> MaxHull::query(ll)':
sequence.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx+1 < lines.size() && lines[idx+1].getVal(x) >= lines[idx].getVal(x)) ++idx;
               ^

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