Submission #951710

#TimeUsernameProblemLanguageResultExecution timeMemory
951710NeltSplit the sequence (APIO14_sequence)C++17
67 / 100
1501 ms85600 KiB
#include <bits/stdc++.h> #define ll long long #define endl "\n" using namespace std; ll intersection(ll k, ll b, ll k1, ll b1) { if (k == k1) return -1; return (ll)((b1 - b) / (k - k1 + 0.0)); } void solve() { ll n, k; cin >> n >> k; ll dp[2][n + 1], a[n + 1]; int best[k + 1][n + 1]; for (ll i = 0; i <= k; i++) for (ll j = 0; j <= n; j++) best[i][j] = 0; a[0] = 0; for (ll i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; for (ll i = 0; i <= n; i++) dp[0][i] = 0, dp[1][i] = -1e18; vector<array<ll, 3>> v; array<ll, 3> cur; for (ll i = 1; i <= k; i++) { v.clear(); for (ll j = 0; j < n; j++) { cur = {0, (ll)1e9, j}; while (!v.empty() and v.back()[0] * a[v.back()[2]] + dp[(i + 1) & 1][v.back()[2]] - a[v.back()[2]] * a[n] < v.back()[0] * a[j] + dp[(i + 1) & 1][j] - a[j] * a[n]) v.pop_back(); if (v.empty()) v.push_back({0, (ll)1e9, j}); else { ll point = intersection(a[v.back()[2]], dp[(i + 1) & 1][v.back()[2]] - a[v.back()[2]] * a[n], a[j], dp[(i + 1) & 1][j] - a[j] * a[n]); if (point != -1) v.back()[1] = point, cur[0] = point + 1, v.push_back(cur); } } for (ll j = 1, pos; j < n; j++) { pos = upper_bound(v.begin(), v.end(), array<ll, 3>{a[j], (ll)1e18, (ll)1e18}) - v.begin(); best[i][j] = 1; for (ll m = max(0ll, pos - 1); m <= min((ll)v.size() - 1, pos + 1); m++) if (dp[i & 1][j] < dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j])) dp[i & 1][j] = dp[(i + 1) & 1][v[m][2]] + (a[j] - a[v[m][2]]) * (a[n] - a[j]), best[i][j] = v[m][2]; } } pair<ll, ll> ans = make_pair(-1, 0); for (ll i = 1; i < n; i++) if (i > k) ans = max(ans, make_pair(dp[k & 1][i], i)); cout << ans.first << endl; ll x = ans.second; for (ll i = k; i >= 1; i--) cout << x << " ", x = best[i][x]; cout << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll t = 1; // precomp(); // cin >> t; for (ll i = 1; i <= t; i++) solve(); cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#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...