WA on #33

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int sum = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -f;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * f;
}
inline void write(int x){
	if(x < 0) putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	return;
}
const int N = 1e5 + 10;
int n, k, s[N], f[N], g[N], fa[201][N];
int head, tail, q[N];
int Y(int i) {return g[i] - s[i] * s[i];}
int X(int i) {return s[i];}
double slope(int i, int j){
	if(X(i) == X(j)) return -1e18;
	return (Y(j) - Y(i)) * 1.0 / (X(j) - X(i));
}
void out(int x, int p){
	if(p < 0) return;
	out(fa[p][x], p - 1);
	write(x), putchar(' ');
	return;
}
signed main(){
	n = read(), k = read();
	for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + read();
	for(int t = 1; t <= k; ++ t){
		for(int i = 1; i <= n; ++ i) g[i] = f[i];
		q[head = tail = 1] = 1;
		for(int i = 2, j; i <= n; ++ i){
			while(head < tail && slope(q[head], q[head + 1]) > - s[i]) ++ head;
			fa[t][i] = j = q[head];
			f[i] = g[j] + s[j] * (s[i] - s[j]);
			while(head < tail && slope(q[tail - 1], q[tail]) < slope(q[tail], i)) -- tail;
			q[++ tail] = i;
		}
	}
	write(f[n]);
	puts("");
	out(fa[k][n], k - 1);
	return 0;
}