Submission #939455

#TimeUsernameProblemLanguageResultExecution timeMemory
939455biximoSplit the sequence (APIO14_sequence)C++17
89 / 100
714 ms85128 KiB
#include <bits/stdc++.h> #define N 100005 using namespace std; typedef long long ll; struct Line { ll m,b; ll get(ll x) { return m*x+b; } long double cross(Line v) { return 1LL*(b-v.b)/(v.m-m); } }; struct CHT { Line vt[N]; int ind[N]; int ft=0,bk=0; void adds(Line v, int i) { while(bk-ft) { if(vt[bk-1].m == v.m) { if(v.b < vt[bk-1].b) { i = ind[bk-1]; v.b = vt[bk-1].b; } --bk; } else { break; } } while(bk-ft >= 2) { if(vt[bk-2].cross(v) < vt[bk-2].cross(vt[bk-1])) { --bk; } else { break; } } ind[bk] = i; vt[bk++] = v; } ll query(int x) { if(bk==ft) { assert(0); } while(bk-ft>=2) { if(vt[ft].cross(vt[ft+1]) < x) { ++ft; } else { break; } } return vt[ft].get(x); } void inits() { ft = 0, bk = 0; } CHT() {} } cht; ll n, k, pref[N], dp[N][2]; int bt[N][205]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; for(int i = 1; i <= n; i ++) { cin >> pref[i]; pref[i] += pref[i-1]; } ll ans = -1, ind; for(int j = 1; j <= k; j ++) { cht.inits(); if(j == 1) { cht.adds({0,0},0); } for(int i = 1; i < j; i ++) { swap(dp[i][0],dp[i][1]); cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i); } for(int i = j; i <= n; i ++) { swap(dp[i][0],dp[i][1]); dp[i][1] = cht.query(pref[i])+pref[n]*pref[i]-pref[i]*pref[i]; bt[i][j] = cht.ind[cht.ft]; if(j == k && ans < dp[i][1]) { ind = i; ans = dp[i][1]; } if(j > 1) { cht.adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i); } } } assert(ind >= k); assert(ans != -1); vector<int> pt; int K = k; while(ind) { pt.push_back(ind); ind = bt[ind][K--]; } if(K) { assert(k == n-1); } cout << ans << "\n"; sort(pt.begin(),pt.end()); for(int i: pt) cout << 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...