| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 7610 | hongjun7 | Split the sequence (APIO14_sequence) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MK 202
#define MN 100002
int N, K, i, j, k, X[MN], _k = 1, best[MK][MN], s[MN], b;
long long d[2][MN], f[MN], S[MN];
bool ok(int z) {
int x = s[b-1], y = s[b];
return (f[y]-f[x])*(S[y]-S[z]) >= (f[z]-f[y]) *(S[x]-S[y]);
}
int main() {
int x;
scanf("%d%d",&N,&K);
for (i = 1; i <= N; i++) {
scanf("%d", &X[i]);
S[i] = S[i-1] + X[i];
}
for (i = 0; i <= N; i++) d[0][i] = -1;
for (k = 2; k <= K+1; k++) {
_k = k&1;
for (i = 0; i <= N; i++) d[_k][i] = 0;
b = -1; x = 1;
s[++b] = 0; s[++b] = 1;
for (i = 0; i <= N; i++) f[i] = d[!(_k)][i]-S[i]*S[i];
for (i = 2; i <= N; i++) {
if (x > b) x = b;
while (x < b && (f[s[x]]-f[s[x+1]]) <= (S[s[x+1]] - S[s[x]])*S[i]) x++;
d[_k][i] = f[s[x]]+S[s[x]]*S[i];
best[k][i] = s[x];
while (b >= x && ok(i)) b--;
s[++b] = i;
}
}
printf("%lld\n",d[_k][N]);
x = N;
for (i = K+1; i > 1; i--) {
x = best[i][x];
res.push_back(x);
}
reverse(res.begin(), res.end());
for (i = 0; i < res.size(); i++) printf("%d ",res[i]);
}