Submission #28741

#	Time	Username	Problem	Language	Result	Execution time	Memory
28741		szawinis	Split the sequence (APIO14_sequence)	C++14	100 / 100	599 ms	88076 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 (l3.c-l1.c)*(l1.m-l2.m) <= (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();
		while(!lines.empty() && lines.back().m == l.m && lines.back().c <= l.c) 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[2][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];
	}
	int curr = 0;
	for(int cnt = 1; cnt <= k; cnt++, curr ^= 1) {
		memset(dp[curr], 0, sizeof(dp[curr]));
		hull.idx = 0;
		hull.lines.clear();
		// hull.update(0, 0, 0); // can do this to get rid of third line in update function
		hull.update(s[cnt], dp[curr^1][cnt] - s[cnt]*s[cnt], cnt);
		for(int i = cnt+1; i <= n; i++) {
			tie(dp[curr][i], trace[cnt][i]) = hull.query(s[i]);
			hull.update(s[i], dp[curr^1][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[curr^1][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:26: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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29