Submission #16558

#	Time	Username	Problem	Language	Result	Execution time	Memory
16558		choyi0521	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	131072 KiB

sequence

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 100000, MAX_K = 200;
int n, k, s[MAX_N + 1];
pair<int, ll> dp[MAX_K + 1][MAX_N + 1];
struct line{
	int m, from;
	ll b;
	line(){}
	line(int _m, ll _b, int _from) :m(_m), b(_b), from(_from){}
}l[MAX_N];
int h, t;
double cross(line l1, line l2){ return (double)(l1.b - l2.b) / (l2.m - l1.m); }
void add(line x){
	while (t - h > 1 && cross(l[t - 2], x) > cross(l[t - 1], x)) t--;
	l[t++] = x;
}
pair<int, ll> f(int x){
	while (t - h > 1 && cross(l[h], l[h + 1]) < x) h++;
	return{ l[h].from, (ll)l[h].m*x + l[h].b };
}
int main(){
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++){
		scanf("%d", &s[i]);
		s[i] += s[i - 1];
	}
	for (int i = 1; i <= k; i++){
		h = t = 0;
		add(line(s[i], dp[i - 1][i].second - (ll)s[i] * s[i], i));
		for (int j = i + 1; j <= n; j++){
			dp[i][j] = f(s[j]);
			add(line(s[j], dp[i - 1][j].second - (ll)s[j] * s[j], j));
		}
	}
	printf("%lld\n", dp[k][n].second);
	vector<int> v;
	for (int i = k, tmp = n; i >= 1; i--){
		tmp = dp[i][tmp].first;
		v.push_back(tmp);
	}
	for (int i = v.size() - 1; i >= 0; i--)
		printf("%d ", v[i]);
	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