Submission #20230

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

sequence

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct Line{
	ll a, b,p;
}line;
const int MAX_N = 1e5, MAX_K = 200;
int n, k, h, t,from[MAX_K+1][MAX_N+1];
ll dp[MAX_K + 1][MAX_N + 1], s1[MAX_N + 1], s2[MAX_N + 1];
line l[MAX_N+1];
double cross(line i, line j) { return (double)(i.b - j.b) / (j.a - i.a); }
void push(line i) {
	while (t - h > 1 && cross(l[t - 1], i) < cross(l[t - 2], i)) t--;
	l[t++] = i;
}
void query(int i,int j) {
	while (t - h > 1 && cross(l[h], l[h + 1]) < s1[j]) h++;
	dp[i][j]=l[h].a*s1[j] + l[h].b+ s1[j] * s1[j] - s2[j];
	from[i][j] = l[h].p;
}
void back(int i,int x) {
	if (!i) return;
	back(i - 1, from[i][x]);
	printf("%d ", x);
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1,x; i <= n; i++) {
		scanf("%d", &x);
		s1[i] = s1[i - 1] + x;
		s2[i] = s2[i - 1] + x*x;
	}
	for (int i = 1; i <= n; i++) dp[1][i] = s1[i] * s1[i] - s2[i];
	for (int i = 2; i <= k + 1; i++) {
		h = t = 0;
		push({ -2 * s1[i - 1],s1[i - 1] * s1[i - 1] + s2[i - 1]+dp[i-1][i-1],i-1});
		for (int j = i; j <= n; j++) {
			query(i, j);
			push({ -2 * s1[j],s1[j] * s1[j] + s2[j]+dp[i-1][j],j});
		}
	}
	printf("%lld\n", (s1[n] * s1[n] - s2[n] - dp[k + 1][n]) / 2);
	back(k,from[k+1][n]);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:28:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
                        ^
sequence.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^

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