Submission #723510

#TimeUsernameProblemLanguageResultExecution timeMemory
723510junseoSplit the sequence (APIO14_sequence)C++17
11 / 100
2062 ms5708 KiB
#include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define ep emplace #define all(v) (v).begin(), (v).end() #define sz(v) (int)v.size() #define rmin(r, x) r = min(r, x) #define rmax(r, x) r = max(r, x) #define ends ' ' #define endl '\n' #define rep(i, s, e) for(int i = (s); i <= (e); ++i) #define rep2(i, e, s) for(int i = (e); i >= (s); --i) #define print(v) copy(all(v), ostream_iterator<int>(cout, " ")), cout << endl #define fastio ios_base::sync_with_stdio(0), cin.tie(0) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<int> vi; // #define LOCAL const ll inf = 1e18; const int maxn = 1e5 + 10; const int maxk = 2e2 + 10; const ll minx = 0, maxx = 1e9; int N, K; ll S[maxn]; ll D[2][maxn]; int P[maxk][maxn]; struct Line { ll a, b; int prv; Line(ll a=0, ll b=-inf, int prv=-1) : a(a), b(b), prv(prv) {} ll calc(ll x) { return a * x + b; } }; struct Node { Line f; int l, r; Node() : l(0), r(r) {} }; struct Lichao { vector<Node> tr; int C; void init() { C = 1; tr.clear(); tr.resize(maxn); } void update(Line g, int nd=1, ll st=minx, ll ed=maxx) { while(true) { Line& f = tr[nd].f; ll mid = st+ed >> 1; if(f.calc(mid) < g.calc(mid)) swap(f, g); if(f.calc(st) < g.calc(st)) { ed = mid-1; nd = tr[nd].l = (tr[nd].l ?: ++C); } else if(f.calc(ed) < g.calc(ed)) { st = mid+1; nd = tr[nd].r = (tr[nd].r ?: ++C); } else break; } } pll query(ll x, int nd=1, ll st=minx, ll ed=maxx) { pll ret = {-inf, -1}; while(nd) { ll mid = st+ed >> 1; rmax(ret, pll(tr[nd].f.calc(x), tr[nd].f.prv)); if(x <= mid) { nd = tr[nd].l; ed = mid-1; } else { nd = tr[nd].r; st = mid+1; } } return ret; } } T; int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif fastio; cin >> N >> K; rep(i, 1, N) { int x; cin >> x; S[i] = S[i-1] + x; } rep(i, 1, N) P[0][i] = i; rep(k, 1, K) { T.init(); int t = k & 1, _t = !t; rep(i, 1, N) { auto [d, p] = T.query(S[i]); D[t][i] = d; P[k][i] = p; T.update(Line(S[i], D[_t][i] - S[i]*S[i], i)); } } vector<int> ans; int idx = N; rep2(k, K, 1) { idx = P[k][idx]; ans.eb(idx); } reverse(all(ans)); cout << D[K&1][N] << endl; for(auto& i : ans) cout << i << ends; return 0; }

Compilation message (stderr)

sequence.cpp: In constructor 'Node::Node()':
sequence.cpp:45:2: warning: 'Node::r' is initialized with itself [-Winit-self]
   45 |  Node() : l(0), r(r) {}
      |  ^~~~
sequence.cpp: In member function 'void Lichao::update(Line, int, ll, ll)':
sequence.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |    ll mid = st+ed >> 1;
      |             ~~^~~
sequence.cpp: In member function 'pll Lichao::query(ll, int, ll, ll)':
sequence.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |    ll mid = st+ed >> 1;
      |             ~~^~~
#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...