#include<stdio.h>
int n,k,top,p,path[210][100010],w,dap[100010];
long long int a[100010],s[100010],d[2][100010];
struct data
{
long long int m,n,pos;
}st[100010];
int main()
{
long long int i,j,r,m1,m2,n1,n2,m3,n3;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for(i=2;i<=k+1;i++)
{
top=1, p=1;
st[1].m=s[1]; st[1].n=-s[1]*s[1]+d[(i+1)%2][1]; st[1].pos=1;
for(j=2;j<=n;j++)
{
m2=s[j]; n2=-s[j]*s[j]+d[(i+1)%2][j];
for(r=p;r<=top-1;r++)
{
m1=st[r+1].m; n1=st[r+1].n; m3=st[r].m; n3=st[r].n;
if(n3-n1>(m1-m3)*s[j]) break;
}
p=r;
d[i%2][j]=st[p].m*s[j]+st[p].n; path[i][j]=st[p].pos;
for(r=top;r>=1;r--)
{
if(r==1) break;
m1=st[r].m; n1=st[r].n; m3=st[r-1].m; n3=st[r-1].n;
if((n1-n2)*(m1-m3)>(m2-m1)*(n3-n1)) break;
top--;
}
top++; st[top].m=m2; st[top].n=n2; st[top].pos=j;
}
}
printf("%lld\n",d[(k+1)%2][n]);
p=n;
for(i=k+1;i>=1;i--)
{
if(p==0) break;
dap[++w]=p;
p=path[i][p];
}
for(i=w;i>=2;i--) printf("%d ",dap[i]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 0 == 0 |
4 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 1542524 == 1542524 |
5 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 4500000000 == 4500000000 |
6 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 1 == 1 |
7 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 1 == 1 |
8 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 1 == 1 |
9 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 100400096 == 100400096 |
10 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 900320000 == 900320000 |
11 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 3698080248 == 3698080248 |
12 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 3200320000 == 3200320000 |
13 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 140072 == 140072 |
14 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 376041456 == 376041456 |
15 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 805 == 805 |
16 |
Correct |
0 ms |
88988 KB |
Output is correct - contestant found the optimal answer: 900189994 == 900189994 |
17 |
Incorrect |
0 ms |
88988 KB |
Output isn't correct - contestant didn't find the optimal answer: 999919991 < 999919994 |
# |
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 |
- |