Submission #1000661

#TimeUsernameProblemLanguageResultExecution timeMemory
1000661vjudge1Split the sequence (APIO14_sequence)C++17
100 / 100
1167 ms90088 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define F first #define S second #define getlast(s) (*s.rbegin()) #define debg cout << "OK\n" const ld PI = 3.1415926535; const int N = 100000+1; const int M = 7e6 + 1; int mod = 998244353; const int infi = INT_MAX; const ll infl = LLONG_MAX; const int P = 31; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { if (a + b < 0) return a + b + mod; if (a + b >= mod) return a + b - mod; return a + b; } ll binpow(ll a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return binpow(a, n - 1) * a % mod; } else { ll b = binpow(a, n / 2); return b * b % mod; } } struct Line{ ll k, b, ind; }; ll intersect(Line x, Line y){ return (ll)ceil((ld)(y.b - x.b) / (ld)(x.k - y.k)); } struct LineContainer : multiset<Line, less<>> { vector<pair<ll, Line>> st; void add(ll k, ll m, ll ind) { if(sz(st) == 0){ st.pb({-infi, {k, m, ind}}); return; } while(k == st.back().S.k || intersect({k, m, ind}, st.back().S) < st.back().F){ if(k == st.back().S.k && st.back().S.b > m) return; st.pop_back(); } st.push_back({intersect({k, m, ind}, st.back().S), {k, m, ind}}); } pair<ll, ll> query(ll x) { int lo = 0, hi = sz(st); while(lo + 1 < hi){ int m = (lo + hi) / 2; if(st[m].F <= x) lo = m; else hi = m; } return {st[lo].S.k * x + st[lo].S.b, st[lo].S.ind}; } }; ll a[N], pr[N]; int p[N][201]; vector<ll> cdp(N, 0LL), pdp(N, 0LL); int n, k; void solve(){ cin >> k; pr[0] = 0; for(int i = 1; i <= n; i++) cin >> a[i], pr[i] = pr[i - 1] + a[i]; for(int l = 1; l <= k; l++){ LineContainer lc; lc.add(pr[l], pdp[l] - pr[l] * pr[l], l); cdp[l] = 0; p[l][l] = 0; for(int i = l + 1; i <= n; i++){ pair<ll, ll> ret = lc.query(pr[i]); cdp[i] = ret.F; p[i][l] = ret.S; lc.add(pr[i], pdp[i] - pr[i] * pr[i], i); } pdp = cdp; } int cur = k, cn = n; vector<int> ans = {}; while(cur > 0){ ans.pb(p[cn][cur]); cn = p[cn][cur]; cur--; } cout << cdp[n] << '\n'; reverse(all(ans)); for(auto e : ans) cout << e << ' '; } struct huinya{ struct Line { mutable ll k, m, p, ind; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m, ll ind) { auto z = insert({k, m, 0, ind}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } pair<ll, ll> query(ll x) { assert(!empty()); auto l = *lower_bound(x); return {l.k * x + l.m, l.ind}; } }; ll a[11], pr[11]; int p[11][201]; vector<ll> cdp, pdp; void solve(){ cdp.assign(n + 1, 0LL); pdp.assign(n + 1, 0LL); int k; cin >> k; pr[0] = 0; for(int i = 1; i <= n; i++) cin >> a[i], pr[i] = pr[i - 1] + a[i]; for(int l = 1; l <= k; l++){ LineContainer lc; lc.add(pr[l], pdp[l] - pr[l] * pr[l], l); cdp[l] = 0; p[l][l] = 0; for(int i = l + 1; i <= n; i++){ pair<ll, ll> ret = lc.query(pr[i]); cdp[i] = ret.F; p[i][l] = ret.S; lc.add(pr[i], pdp[i] - pr[i] * pr[i], i); } pdp = cdp; } int cur = k, cn = n; vector<int> ans = {}; while(cur > 0){ ans.pb(p[cn][cur]); cn = p[cn][cur]; cur--; } cout << cdp[n] << '\n'; reverse(all(ans)); for(auto e : ans) cout << e << ' '; } }; signed main() { mispertion; int t = 1; //cin >> t; while(t--){ cin >> n; if(n <= 10){ huinya h; h.solve(); }else{ solve(); } } return 0; }
#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...