Submission #698176

#TimeUsernameProblemLanguageResultExecution timeMemory
698176tvladm2009Split the sequence (APIO14_sequence)C++17
0 / 100
14 ms3132 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = (int) 1e5 + 7; const int K = (int) 2e2 + 7; int a[N], sp[N], dp[2][K], rec[2][K]; struct Line { int a; int b; int ind; int eval(int x) { return a * x + b; } }; struct Fraction { int num; ll den; }; Fraction x(Line l1, Line l2) { // l1.a * x + l1.b = y // l2.a * x + l2.b = y // l1.a * x + l1.b = l2.a * x + l2.b // l1.a * x - l2.b * x = l2.b - l1.b // (l1.a - l2.b) * x = l2.b - l1.b // x = (l2.b - l1.b) / (l1.a - l2.a) if (l1.a - l2.a > 0) { return {l2.b - l1.a, l1.a - l2.a}; } else { return {-(l2.b - l1.b), -(l1.a - l2.a)}; } } bool operator <= (const Fraction &a, const Fraction &b) { return a.num * b.den <= a.den * b.num; } deque<Line> DS; void add(Line line) { while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) { DS.pop_back(); } DS.push_back(line); } pair<ll, int> query(int x) { while ((int) DS.size() >= 2 && DS[0].eval(x) <= DS[1].eval(x)) { DS.pop_front(); } return {DS[0].eval(x), DS[0].ind}; } void solve(int layer, int n) { DS.clear(); for (int i = layer; i <= n; i++) { add({sp[i - 1], dp[(layer & 1) ^ 1][i - 1] - sp[i - 1] * sp[i - 1], i - 1}); pair<int, int> aux = query(sp[i]); dp[layer & 1][i] = aux.first; rec[layer & 1][i] = aux.second; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { sp[i] = sp[i - 1] + a[i]; dp[1][i] = 0; } for (int i = 2; i <= k + 1; i++) { solve(i, n); } cout << dp[(k + 1) & 1][n] << "\n"; vector<int> sol; int aux = rec[k & 1][n]; while (k > 0) { sol.push_back(aux); aux = rec[k & 1][aux]; k--; } reverse(sol.begin(), sol.end()); for (auto &it : sol) { cout << it << " "; } 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...