Submission #6868

#TimeUsernameProblemLanguageResultExecution timeMemory
6868woqja125Split the sequence (APIO14_sequence)C++98
0 / 100
0 ms131072 KiB
#include<stdio.h> int dat[100001], s[100001]; long long dp[210][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<=k; i++)for(j=0; j<=n; j++) dp[i][j]=-1; dp[0][0] = 0; for(i=1; i<=k; i++) { for(j=1; j<=n; j++) { long long max = 0; int x = -1; for(l=0; l<j; l++) { if(dp[i-1][l] == -1) continue; long long t = dp[i-1][l] - 1ll*s[l]*s[l] + 1ll*s[l]*s[j]; if(max < t) { max = t; x = l; } } p[i][j] = x; dp[i][j] = max; } } printf("%lld\n", dp[k][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...