#include<stdio.h>
int dat[100001], s[100001];
long long dp[2][100001];
int p[210][100001];
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;
dp[0][0] = 0;
for(i=1; i<=k; i++)
{
for(j=0; j<=n; j++) dp[i%2][j]=-1;
for(j=1; j<=n; j++)
{
long long max = 0;
int x = -1;
long long *D = dp[(i-1)%2];
for(l=0; l<j; l++)
{
if(D[l] == -1) continue;
long long t = D[l] - 1ll*s[l]*s[l] + 1ll*s[l]*s[j];
if(max < t)
{
max = t;
x = l;
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
85464 KB |
Output is correct - contestant found the optimal answer: 108 == 108 |
| 2 |
Correct |
0 ms |
85464 KB |
Output is correct - contestant found the optimal answer: 999 == 999 |
| 3 |
Incorrect |
0 ms |
85464 KB |
Output isn't correct - Integer -1 violates the range [1, 1] |
| 4 |
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 |
- |
