제출 #938570

#제출 시각아이디문제언어결과실행 시간메모리
938570Xiaoyang수열 (APIO14_sequence)C++17
0 / 100
431 ms118196 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second #define pll pair<ll,ll> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl; #define MP make_pair #define rep(i,a,b) for(ll i=a;i<b;i++) #define ALL(x) x.begin(),x.end() #define endl "\n" const ll inf=1e18; const ll maxn=11111; ll dp[maxn][222]; ll a[maxn],pre[maxn]; pll fa[maxn][222]; void dfs(pll u){ if(u==MP(0ll,0ll))return; dfs(fa[u.fi][u.se]); cout<<u.fi<<" "; } int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n,K;cin>>n>>K; rep(i,1,n+1)cin>>a[i]; rep(i,1,n+1)pre[i]=pre[i-1]+a[i]; rep(k,1,K+1){ rep(i,1,n+1){ rep(j,1,i){ if(dp[j][k-1]+(pre[i]-pre[j])*(pre[n]-pre[i])>dp[i][k]){ dp[i][k]=dp[j][k-1]+(pre[i]-pre[j])*(pre[n]-pre[i]); fa[i][k]=MP(j,k-1); } } } } /* rep(i,1,n+1){ rep(j,0,K+1)cout<<dp[i][j]<<" "; cout<<endl; } */ ll mx=-inf; pll p=MP(0ll,0ll); rep(i,1,n+1){ if(dp[i][K]>mx){ mx=dp[i][K]; p=MP(i,K); } } cout<<mx<<endl; dfs(p); 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...