Submission #1150378

#TimeUsernameProblemLanguageResultExecution timeMemory
1150378hahahoang132수열 (APIO14_sequence)C++20
100 / 100
893 ms87412 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const ll N = 1e5 + 5; const ll base = 37; const ll inf = LLONG_MAX/4; const ll mod = 1e9 + 7; #define bit(x,y) ((x >> y) & 1) struct ConvexHullTrick { const ll Inf = 1e18; ll n; ll a[N], b[N], id[N]; vector<ll> line; vector<ld> poll; ConvexHullTrick() { poll.emplace_back(-Inf); } void clea() { line.clear(); poll.clear(); poll.emplace_back(-Inf); } ld ff(ll x, ll y) { return (ld) 1.0 * (b[x] - b[y]) / (a[y] - a[x]); } void Add(ll i) { while (!line.empty()) { if (a[line.back()] == a[i]) { if (b[line.back()] < b[i]) { break; } else { line.pop_back(); if (!line.empty()) { poll.pop_back(); } } } else { if (line.size() < 2) { break; } if (ff(i, line[line.size() - 2]) < ff(i, line.back())) { break; } else { line.pop_back(); if (!line.empty()) { poll.pop_back(); } } } } if (line.empty() || a[line.back()] != a[i]) { if (!line.empty()) { poll.emplace_back(ff(i, line.back())); } line.emplace_back(i); } } pair<ll,ll> get(ll x) { ll j = upper_bound(poll.begin(), poll.end(), (ld) x) - poll.begin() - 1; return {a[line[j]] * x + b[line[j]],id[line[j]]}; } }; ll a[N],s[N]; ll d[2][N]; int v[205][N]; ConvexHullTrick f; int main() { ll n,k; cin >> n >> k; ll i,j; for(i = 1;i <= n;i++) cin >> a[i]; for(i = 1;i <= n;i++) s[i] = s[i - 1] + a[i]; f.n = n + 5; ll e = 0; for(i = 2;i <= k + 1;i++) { f.clea(); for(j = i;j <= n;j++) { f.a[j - i + 1] = s[j - 1]; f.b[j - i + 1] = d[e][j - 1] - (s[j - 1] * s[j - 1]); f.id[j - i + 1] = j - 1; f.Add(j - i + 1); pair<ll,ll> tmp = f.get(s[j]); d[1 - e][j] = tmp.first; v[i][j] = tmp.second; } e = 1 - e; } cout << d[e][n] << "\n"; i = k + 1; j = n; while(i > 1) { cout << v[i][j] << " "; j = v[i][j]; i--; } }
#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...