Submission #5860

#	Time	Username	Problem	Language	Result	Execution time	Memory
5860		gs12037	Split the sequence (APIO14_sequence)	C++98	100 / 100	652 ms	90196 KiB

sequence

#include <stdio.h>
#include <algorithm>
#include <vector>
#define M 100004
#define INF 1234567890
using namespace std;
int n, k;
struct pp{
	long long int a, b;
	int pos;
};
vector<pp> v;
long long int d[2][M], ans, s[M];
int path[209][M], pri[M];
int main(){
	int i, j;
	pp e;
	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++) scanf("%lld", &s[i]);
	for (i = 1; i <= n; i++) s[i] = s[i - 1] + s[i];

	for (i = 1; i <= k; i++){
		v.clear();
		for (j = i; j <= n; j++){
			e.a = s[j]; e.b = d[0][j] - (long long)s[j] * s[j]; e.pos = j;
			while (v.size() > 1){
				int EE = v.size() - 1;
				if ((v[EE].a - v[EE - 1].a)*(e.b - v[EE].b) >= (e.a - v[EE].a)*(v[EE].b - v[EE - 1].b)) v.pop_back();
				else break;
			}
			v.push_back(e);
		}
		e.a = 0; e.b = -INF; e.pos = 0; v.push_back(e);
		int pivot = 0;
		for (j = i; j <= n; j++){
			while (s[j] * v[pivot].a + v[pivot].b <= s[j] * v[pivot + 1].a + v[pivot + 1].b && v[pivot + 1].pos < j) pivot++;
			d[1][j] = s[j] * v[pivot].a + v[pivot].b;
			path[i][j] = v[pivot].pos;
		}
		for (j = i; j <= n; j++) d[0][j] = d[1][j];
	}
	printf("%lld\n", d[1][n]);
	int temp = path[k][n];
	for (i = k; i >= 1; i--){
		pri[i] = temp;
		temp = path[i - 1][temp];
	}
	for (i = 1; i <= k; i++) printf("%d ", pri[i]);
}

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