Submission #379581

#TimeUsernameProblemLanguageResultExecution timeMemory
379581Aryan_RainaSplit the sequence (APIO14_sequence)C++14
0 / 100
675 ms131076 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define ar array const int INF = LLONG_MAX; const int MOD = 1e9+7; const int MXN = 1e5+9, MXK = 205; int dp[2][MXN], par[MXK][MXN]; struct CHT { struct Line { int m, c, index; Line(int _m, int _c, int _index) : m(_m), c(_c), index(_index) {} ld intersect(Line other) { return (ld) (c - other.c)/(other.m - m); } int at(int x) { return m*x + c; } }; deque<Line> dq; void add(int m, int c, int index) { Line newLine(m, c, index); while (dq.size() >= 2 && dq[1].intersect(newLine) >= dq[1].intersect(dq[0])) { dq.pop_front(); } dq.push_front(newLine); } ar<int,2> query(int x) { // {m*x + c, index} while (dq.size() >= 2 && end(dq)[-1].at(x) <= end(dq)[-2].at(x)) { dq.pop_back(); } return {dq.back().at(x), dq.back().index}; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin>>n>>k; vector<int> v(n); for (int &i : v) cin>>i; vector<int> pf(n); partial_sum(v.begin(), v.end(), pf.begin()); auto sum = [&](int l, int r) { return pf[r] - (l-1 >= 0 ? pf[l-1] : 0); }; CHT cht; cht.add(0, 0, 0); for (int i = 1; i <= k; i++) { int I = i&1; for (int j = 1; j < n; j++) { // for (int a = 0; a < j; a++) { // if (dp[I][j] < dp[I^1][a] + sum(a, j-1)*sum(j, n-1)) { // dp[I][j] = dp[I^1][a] + sum(a, j-1)*sum(j, n-1); // par[i][j] = a; // } // } ar<int,2> qry = cht.query(sum(j, n-1)); dp[I][j] = qry[0] + pf[j-1]*sum(j, n-1); par[i][j] = qry[1]; cht.add(-pf[j-1], dp[I^1][j], j); } } int ans = 0, x = 0; for (int j = 0; j < n; j++) { if (dp[k&1][j] > ans) { ans = dp[k&1][j]; x = j; } } cout<<ans<<"\n"; vector<int> bruh; int lmao = k; while (x) { bruh.push_back(x); x = par[lmao--][x]; } for (int i = bruh.size()-1; i >= 0; --i) cout<<bruh[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...