Submission #95808

#TimeUsernameProblemLanguageResultExecution timeMemory
95808fedoseevtimofeySplit the sequence (APIO14_sequence)C++14
100 / 100
644 ms84148 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; struct line { ll k, b; line (ll k, ll b) : k(k), b(b) {} }; ll f(const line &l, ll x) { return l.k * x + l.b; } ld inter(const line &a, const line &b) { return (ld)(a.b - b.b) / (b.k - a.k); } vector <line> s; vector <int> idx; int ptr = 0; void push(const line &l, int id) { while ((int)s.size() && s[(int)s.size() - 1].k == l.k && s[(int)s.size() - 1].b <= l.b) { s.pop_back(); idx.pop_back(); } if (!s.empty() && s.back().k == l.k && s.back().b > l.b) return; while ((int)s.size() >= 2) { line a = s[(int)s.size() - 1]; line b = s[(int)s.size() - 2]; if (inter(l, a) <= inter(l, b)) { s.pop_back(); idx.pop_back(); } else { break; } } s.push_back(l); idx.push_back(id); } pair <ll, int> get(ll x) { ptr = min(ptr, (int)s.size() - 1); while (ptr + 1 < (int)s.size() && f(s[ptr], x) <= f(s[ptr + 1], x)) ++ptr; return {f(s[ptr], x), idx[ptr]}; } const ll Inf = 2e18; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n, k; cin >> n >> k; vector <int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector <ll> dp(n + 1, -Inf); dp[0] = 0; vector <ll> pref(n + 1); for (int i = 0; i < n; ++i) { pref[i + 1] = pref[i] + a[i]; } vector <vector <int>> who(k + 1, vector <int> (n + 1, -1)); for (int j = 1; j <= k; ++j) { ptr = 0; s.clear(); idx.clear(); push(line(pref[0], -pref[0] * pref[n] + dp[0]), 0); dp[0] = -Inf; for (int i = 1; i <= n; ++i) { auto p = get(pref[i]); push(line(pref[i], -pref[i] * pref[n] + dp[i]), i); dp[i] = p.first + pref[i] * (pref[n] - pref[i]); who[j][i] = p.second; } } ll ans = -1; int id = -1; for (int i = 1; i < n; ++i) { if (dp[i] > ans) { ans = dp[i]; id = i; } } vector <int> where; for (int cr = k; cr >= 1; --cr) { where.push_back(id); id = who[cr][id]; } reverse(where.begin(), where.end()); cout << ans << '\n'; for (auto x : where) { cout << x << ' '; } }
#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...