#include<stdio.h>
int dat[100001], s[100001];
long long dp[2][100001];
long long Y[100001];
int p[210][100001];
int stk[100001], b;
inline bool cmp(long long *D, int z)
{
int x, y;
x = stk[b-1];
y = stk[b];
return (Y[y]-Y[x])*(s[y]-s[z]) >= (Y[z]-Y[y]) *(s[x]-s[y]);
}
int main()
{
int n, k;
int i, j, l;
scanf("%d%d", &n, &k); k++;
for(i=1; i<=n; i++)
{
scanf("%d", &dat[i]);
s[i] = s[i-1] + dat[i];
}
for(i=0; i<=1; i++)for(j=0; j<=n; j++) dp[i][j]=-1;
for(j=0; j<=n; j++)
{
dp[1][j] = 0;
}
for(i=2; i<=k; i++)
{
for(j=0; j<=n; j++) dp[i%2][j]=0;
long long *D = dp[(i-1)%2];
b = -1;
int x=1;
stk[++b] = 0; stk[++b] = 1;
for(j=0; j<=n; j++) Y[j] = D[j] - 1ll*s[x]*s[x];
for(l=2; l<=n; l++)
{
if(x>b) x = b;
while(x < b && (Y[stk[x]] - Y[stk[x+1]]) <= 1ll*(s[stk[x+1]] - s[stk[x]])*s[l] ) x++;
dp[i%2][l] = D[stk[x]] - 1ll*s[stk[x]]*s[stk[x]] + 1ll*s[stk[x]]*s[l];
p[i][l] = stk[x];
while( b>=x && cmp(D, l) ) b--;
stk[++b] = l;
}
}
printf("%lld\n", dp[k%2][n]);
int x = n;
for(int i=k; i>1; i--)
{
x = p[i][x];
printf("%d ", x);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
86636 KB |
Output isn't correct - contestant didn't find the optimal answer: 98 < 108 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
