제출 #7914

#제출 시각아이디문제언어결과실행 시간메모리
7914woqja125수열 (APIO14_sequence)C++98
100 / 100
1340 ms86244 KiB
#include<stdio.h> int dat[100001], sum[100001]; long long dp[2][100001]; long long Y[100001]; int p[210][100001]; void mkt(long long *T, long long *S, int *p, int f, int r, int s, int e) { if(f>r) return; long long max = -1, t; int x = -1, i, m = (f+r)/2; for(i=s; i<=e && i<m; i++) { if(S[i] == -1) continue; t = S[i] + (1ll*sum[i]*(sum[m] - sum[i])); if(t>=max) { max = t; x = i; } } T[m] = max; p[m] = x; mkt(T, S, p, f, m-1, s, x); mkt(T, S, p, m+1, r, x, e); } int main() { int n, k, i, j; scanf("%d%d", &n, &k); k++; for(i=1; i<=n; i++) { scanf("%d", &dat[i]); sum[i] = sum[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; mkt(dp[i%2], dp[(i+1)%2], p[i], 0, n, 0, n); } 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...