제출 #535187

#제출 시각아이디문제언어결과실행 시간메모리
535187ala2수열 (APIO14_sequence)C++14
22 / 100
2074 ms131072 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n,m; int a[1001000]; int p[1001000]; int dp[205][205][205]; int f(int i,int j,int k) { if(k==0) return 0; if(i==j) return 0; if(dp[i][j][k]!=-1) return dp[i][j][k]; 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 dp[i][j][k]=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() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); memset(dp,-1,sizeof dp); 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...