제출 #6914

#제출 시각아이디문제언어결과실행 시간메모리
6914dohyun0324수열 (APIO14_sequence)C++98
100 / 100
564 ms88988 KiB
#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; 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[i-1]; st[1].n=-s[i-1]*s[i-1]+d[(i+1)%2][i-1]; st[1].pos=i-1; for(j=i;j<=n;j++) { m2=s[j]; n2=-s[j]*s[j]+d[(i+1)%2][j]; if(p>top) p=top; 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=r; 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--) { dap[++w]=p; p=path[i][p]; } for(i=w;i>=2;i--) printf("%d ",dap[i]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...