제출 #344481

#제출 시각아이디문제언어결과실행 시간메모리
344481wwdd수열 (APIO14_sequence)C++14
0 / 100
69 ms131076 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; const int MN = 100100; const int MK = 222; const ll INFL = 1e18; vl w,pr; ll dp[MK][MN]; ll pd[MK][MN]; void ds(ll ro, ll l, ll r, ll kl, ll kr) { if(l > r) {return;} ll m = (l+r)/2; ll mo = kl; ll mv = -1; for(int i=kl;i<=min(m-1,kr);i++) { ll pk = dp[ro-1][i] + pr[i]*(pr[m]-pr[i]); if(pk > mv) {mv = pk;mo = i;} } dp[ro][m] = mv; pd[ro][m] = mo; ds(ro,l,m-1,kl,mo); ds(ro,m+1,r,mo,kr); } int main() { ios::sync_with_stdio(0);cin.tie(0); memset(dp,0,sizeof(dp)); int n,k; cin >> n >> k; pr.push_back(0); for(int i=0;i<n;i++) { ll t; cin >> t; w.push_back(t); pr.push_back(pr.back()+t); } for(int i=1;i<=k;i++) { ds(i,i+1,n,i,n); } vl res; ll bak = n; for(int i=k;i>0;i--) { res.push_back(pd[i][bak]); bak = res.back(); } cout << dp[k][n] << '\n'; reverse(res.begin(),res.end()); for(int i=0;i<k;i++) { if(i > 0) {cout << " ";} cout << res[i]; } cout << '\n'; }
#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...