제출 #1000949

#제출 시각아이디문제언어결과실행 시간메모리
1000949vjudge1Split the sequence (APIO14_sequence)C++17
71 / 100
54 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define ar array #define pb push_back #define ln '\n' #define int long long using i64 = long long; template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } struct Line{ int m, c, idx; Line(int m = 0, int c = 0, int idx = 0) : m(m), c(c), idx(idx) {} int operator ()(int x){ return m * x + c; } long double operator ^(const Line &t){ return (c - t.c + .0) / (t.m - m); } bool isOpt(Line ff, Line ss){ __int128 p = c - ff.c, q = c - ss.c; p *= ss.m - m, q *= ff.m - m; return p <= q; }; }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector <int> a(n), pf(n + 1); for ( auto &u: a ){ cin >> u; } for ( int i = 0; i < n; i++ ){ pf[i + 1] = pf[i] + a[i]; } vector <vector<int>> fa(n + 1, vector <int> (k + 1)); vector <int> dp(n + 1); for ( int j = 1; j <= k; j++ ){ auto nxt = dp; deque <Line> dq; auto ins = [&](int j){ Line nw = {pf[j], dp[j] - pf[j] * pf[j], j}; while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(nw, dq.back()) ){ dq.pop_back(); } dq.pb(nw); }; ins(0); for ( int i = 1; i <= n; i++ ){ while ( dq.size() > 1 && dq[0](pf[i]) <= dq[1](pf[i]) ){ dq.pop_front(); } nxt[i] = dq[0](pf[i]); fa[i][j] = dq[0].idx; ins(i); } swap(dp, nxt); } vector <int> ans; int x = n; for ( int i = k; i > 0; i-- ){ ans.pb(fa[x][i]); x = fa[x][i]; } reverse(all(ans)); cout << dp.back() << ln; for ( auto &u: ans ){ cout << u << ' '; } cout << '\n'; } /* 7 3 4 1 3 4 0 2 3 */
#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...