#include<stdio.h>
int dat[100001], s[100001];
long long dp[2][100001];
int p[210][100001];
int stk[100001], b;
inline long long getY(long long *D, int x)
{
return D[x] - 1ll*s[x]*s[x];
}
inline bool cmp(long long *D, int z)
{
int x, y;
x = stk[b-1];
y = stk[b];
return (getY(D, y)-getY(D, x))*(s[y]-s[z]) > (getY(D, z)-getY(D, 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]=-1;
long long *D = dp[(i-1)%2];
b = -1;
int x=0;
stk[++b] = 0; stk[++b] = 1;
for(l=2; l<=n; l++)
{
if(x>b) x = b;
while(x < b && (getY(D, stk[x]) -getY(D, 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( cmp(D, l) ) b--;
stk[++b] = l;
}
for(l; j<=n; j++)
{
long long max = -1;
int x = -1;
p[i][j] = x;
dp[i%2][j] = max;
}
}
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
85852 KB |
Output is correct - contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
0 ms |
85852 KB |
Output is correct - contestant found the optimal answer: 999 == 999 |
| 3 |
Incorrect |
0 ms |
85852 KB |
Output isn't correct - Integer 0 violates the range [1, 1] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
