제출 #982972

#제출 시각아이디문제언어결과실행 시간메모리
982972Hugo1729수열 (APIO14_sequence)C++11
0 / 100
2104 ms102844 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll pref[100001]={0}; ll dp[100001][202]={0}; ll p[100001][202]={0}; struct line{ ll m,c; line(ll _m, ll _c){m=_m;c=_c;} ll intersect(line l){ return m-l.m==0 ? LLONG_MAX/4 : (l.c-c)/(m-l.m); } ll value(ll x){ return m*x+c; } }; deque<pair<line,ll>> q; deque<ll> pos; void insert(ll m, ll c){ line l(m,c); while(!q.empty()&&q.front().second>=l.intersect(q.front().first)){ // cout << "irem" << ' ' << q.front().first.m << ' ' << q.front().first.c << ' ' << q.front().second << '\n'; q.pop_front(); pos.pop_front(); } if(q.empty()){ q.push_front({l,0}); }else{ q.push_front({l,l.intersect(q.front().first)}); } // cout << "iadd" << ' ' << q.front().first.m << ' ' << q.front().first.c << ' ' << q.front().second << '\n'; } ll query(ll x){ while(q.size()>1&&q[q.size()-2].second<=x){ // cout << "qrem" << ' ' << q.back().first.m << ' ' << q.back().first.c << ' ' << q.back().second << '\n'; q.pop_back(); pos.pop_back(); } // cout << "query" << ' ' << q.back().first.m << ' ' << q.back().first.c << ' ' << q.back().second << ' ' << q.back().first.value(x) <<'\n'; return q.back().first.value(x); } int main(){ cin.tie(0)->sync_with_stdio(0); ll n,k; cin >> n >> k; vector<ll> a(n); for(ll i=0;i<n;i++)cin >> a[i]; for(ll i=0;i<n;i++)pref[i+1]=pref[i]+a[i]; for(ll j=1;j<=k+1;j++){ // q.clear(); // pos.clear(); // insert(0,0); // pos.push_front(0); for(ll i=1;i<=n;i++){ for(int x=0;x<i;x++){ if(dp[x][j-1]+(pref[i]-pref[x])*(pref[n]-pref[i])>=dp[i][j]){ dp[i][j]=dp[x][j-1]+(pref[i]-pref[x])*(pref[n]-pref[i]); p[i][j]=x; } } // dp[i][j]=query(pref[i]); // p[i][j]=pos.back(); // insert(pref[i],dp[i][j-1]-pref[i]*pref[i]); // pos.push_front(i); // cout << '(' << i << j <<')' <<dp[i][j] << ' ' << p[i][j] << ' '; } // cout << '\n'; } cout << dp[n][++k] << '\n'; ll sus=n; vector<ll> ans; while(k>1){ ans.push_back(p[sus][k--]); sus=p[sus][k]; } for(ll i=ans.size()-1;i>=0;i--)cout << ans[i] << ' '; return 0; // 7 3 // 4 1 3 4 0 2 3 // (11)0 (21)4 (31)16 (41)35 (51)35 (61)48 (71)72 // (12)0 (22)4 (32)19 (42)48 (52)48 (62)64 (72)95 // (13)0 (23)4 (33)19 (43)51 (53)51 (63)72 (73)108 // 108 }
#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...