제출 #723524

#제출 시각아이디문제언어결과실행 시간메모리
723524junseo수열 (APIO14_sequence)C++17
62 / 100
683 ms81612 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; 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 CHT { deque<Line> f; void update(Line g) { // while(not f.empty() and f.back().a == g.a) { // if(f.back().b > g.b) return; // f.pop_back(); // } if(not f.empty() and f.back().a == g.a and f.back().b >= g.b) return; while(sz(f) >= 2) { Line& t2 = f[sz(f)-2]; Line& t1 = f[sz(f)-1]; // point(2, 0) < point(1, 0): break if((__int128)(t1.b-t2.b)*(t2.a-g.a) < (__int128)(g.b-t2.b)*(t2.a-g.a)) break; f.pop_back(); } f.eb(g); } pll query(ll x) { if(f.empty()) return pll(-inf, -1); while(sz(f) >= 2 and f[0].calc(x) <= f[1].calc(x)) f.pop_front(); return pll(f.front().calc(x), f.front().prv); } } cht; 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) { int t = k & 1, _t = !t; CHT cht; rep(i, 1, N) { auto [d, p] = cht.query(S[i]); D[t][i] = d; P[k][i] = p; cht.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; }
#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...