제출 #1017183

#제출 시각아이디문제언어결과실행 시간메모리
1017183Gray수열 (APIO14_sequence)C++17
89 / 100
801 ms95936 KiB
#include <algorithm> #include <cassert> #include <cstring> #include <deque> #include <ios> #include <iostream> #include <map> #include <vector> #define ll long long #define ull unsigned ll #define ld long double #define ff first #define ss second #define ln "\n" #define pll pair<ll, ll> using namespace std; struct fun{ ll m, c, i; fun(ll _m, ll _c, ll _i):m(_m), c(_c), i(_i){} ll f(ll x){ return m*x+c; } ld inter(ll _m, ll _c){ return ((ld)(_c)-(ld)(c))/((ld)(m)-(ld)(_m)); } }; struct CHT{ deque<fun> que; void add(ll m, ll c, ll i){ if (que.size()<2){ que.push_back(fun(m, c, i)); }else{ while (que.size()>1 and que.back().inter(m, c)<=que[que.size()-2].inter(m, c)) que.pop_back(); que.push_back(fun(m, c, i)); } } pair<ll, ll> query(ll x){ while (que.size()>1 and que[0].f(x)<=que[1].f(x)) que.pop_front(); return {que[0].f(x), que[0].i}; } }; vector<ll> pref(100001), dp(100001); vector<CHT> chts(201); int link[100001][201]; // void get(ll l, ll r, ll optl, ll optr, ll n, ll k){ // if (l>r) return; // ll m = (l+r)/2; // pll optm = {-1, -1}; // for (ll i=optl; i<=min(m-1, optr); i++){ // optm = max(optm, {dep[i]+(pref[m]-pref[i])*(pref[n]-pref[m]), i}); // } // wr[m]=optm.ff; // assert(optm.ss!=-1); // link[m][k]=(int)(optm.ss); // get(l, m-1, optl, optm.ss, n, k); // get(m+1, r, optm.ss, optr, n, k); // } void solve(){ memset(link, 0, sizeof(link)); ll n, k; cin >> n >> k; for (ll i=1; i<=n; i++){ cin >> pref[i]; pref[i]+=pref[i-1]; } for (ll i=1; i<=n; i++){ for (ll j=1; j<=k; j++){ if (j==1){ if (j==k) dp[i]=pref[i]*(pref[n]-pref[i]); chts[j].add(pref[i],pref[i]*(pref[n]-pref[i])-pref[i]*pref[n], i); }else{ auto rdp = chts[j-1].query(pref[i]); if (j==k) dp[i]=rdp.ff+(pref[i]*pref[n]-pref[i]*pref[i]); link[i][j]=(int)rdp.ss; chts[j].add(pref[i], rdp.ff+(pref[i]*pref[n]-pref[i]*pref[i])-pref[i]*pref[n], i); } } } pll best = {-1, -1}; for (ll i=1; i<n; i++){ best=max(best, {dp[i], i}); } vector<ll> ans; for (ll i=k; i>=1; i--){ ans.push_back(best.ss); best.ss=link[best.ss][i]; } cout << best.ff << ln; for (ll i=k-1; i>=0; i--) cout << ans[i] << " "; cout << ln; } // dp[i][k] = maxj(dp[j][k-1]+(pref[i]-pref[j])*(pref[n]-pref[i])); // dp[j][k-1]+pref[i]*pref[n]-pref[i]*pref[i]-pref[j]*pref[n]+pref[j]*pref[i]; // (dp[j][k-1]-pref[j]*pref[n])+(pref[j]*pref[i]) + (pref[i]*pref[n]-pref[i]*pref[i]); int main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); ll t=1; // cin >> t; while (t--)solve(); }
#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...