제출 #6981

#제출 시각아이디문제언어결과실행 시간메모리
6981woqja125수열 (APIO14_sequence)C++98
0 / 100
0 ms86636 KiB
#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 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...