Submission #535185

#TimeUsernameProblemLanguageResultExecution timeMemory
535185ala2Split the sequence (APIO14_sequence)C++14
11 / 100
2092 ms1748 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n,m; int a[1001000]; int p[1001000]; int f(int i,int j,int k) { if(k==0) return 0; if(i==j) return 0; int g=0; for(int ii=i; ii<j; ii++) { for(int kk=0; kk<k; kk++) { int x=p[ii]-p[i-1]; int y=p[j]-p[ii]; g=max(g, f(i,ii,kk)+f(ii+1,j,k-kk-1)+x*y); } } return g; } vector<int>v; void d(int i,int j,int k) { if(k==0) return ; if(i==j) return ; for(int ii=i; ii<j; ii++) { for(int kk=0; kk<k; kk++) { int x=p[ii]-p[i-1]; int y=p[j]-p[ii]; // cout<<" "<<f(i,ii,kk)<<" "<<f(ii+1,j,k-kk-1)<<" "<< x*y << " "<<f(i,j,k)<<endl; if( f(i,ii,kk) + f(ii+1,j,k-kk-1) + x*y ==f(i,j,k)) { v.push_back(ii); d(i,ii,kk); d(ii+1,j,k-kk-1); return ; } } } } signed main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; p[i]=a[i]+p[i-1]; } cout<<f(1,n,m)<<endl; d(1,n,m); for(auto i:v) cout<<i<<" " ; }
#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...