Submission #18452

#TimeUsernameProblemLanguageResultExecution timeMemory
18452tlwpdusSplit the sequence (APIO14_sequence)C++98
0 / 100
0 ms85856 KiB
/* O(N^2*K) */ #include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; int n, m; int arr[100010]; ll psum[100010]; ll dyn[2][100010]; int via[210][100010]; void process() { int i, j, k; for (i=1;i<=n;i++) dyn[0][i] = psum[i]*(psum[n]-psum[i]); for (i=2;i<=m;i++) { for (j=i;j<n;j++) { for (k=1;k<j;k++) { ll val = dyn[0][k]+(psum[j]-psum[k])*(psum[n]-psum[j]); if (dyn[1][j]<val) { dyn[1][j] = val; via[i][j] = k; } } } for (j=1;j<=n;j++) {dyn[0][j] = dyn[1][j];dyn[1][j]=0;} } ll maxi = 0; int idx = -1; for (i=1;i<n;i++) { if (maxi<dyn[0][i]) { maxi = dyn[0][i]; idx = i; } } printf("%lld\n",maxi); for (i=m;i>0;idx=via[i--][idx]) printf("%d ",idx); printf("\n"); } void input() { int i; scanf("%d %d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",&arr[i]); psum[i] = psum[i-1]+arr[i]; } } int main() { input(); process(); 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...