Submission #97723

#TimeUsernameProblemLanguageResultExecution timeMemory
97723dalgerokSplit the sequence (APIO14_sequence)C++14
100 / 100
760 ms84692 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, a[N], pref[N]; int pr[202][N]; struct line{ long long k, b; int pos; inline long long val(int x){ return k * x + b; } }; line q1[N], q2[N]; int sz1, sz2; inline long long intersect(line l1, line l2){ return (l1.b - l2.b) / (l2.k - l1.k); } inline bool Is_need_to_erase(line l1, line l2, line l3){ long long x = intersect(l1, l3); return l2.val(x) <= l3.val(x); } inline void Add(line new_line){ if(sz1 && q1[sz1 - 1].k == new_line.k){ if(q1[sz1 - 1].b < new_line.b){ sz1 -= 1; } else{ return; } } while(sz1 > 2 && Is_need_to_erase(q1[sz1 - 2], q1[sz1 - 1], new_line)){ sz1 -= 1; } q1[sz1] = new_line; sz1 += 1; } inline void Swap(){ swap(q1, q2); swap(sz1, sz2); sz1 = 0; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } for(int i = 1; i <= n; i++){ Add({pref[i], -(1LL * pref[i] * pref[i]), i}); } Swap(); long long ans = 0; for(int i = 1; i <= m; i++){ int pos = 0; for(int j = i + 1; j <= n; j++){ while(pos + 1 < sz2 && q2[pos + 1].pos < j && q2[pos].val(pref[j]) <= q2[pos + 1].val(pref[j])){ pos += 1; } pr[i][j] = q2[pos].pos; ans = q2[pos].val(pref[j]); Add({pref[j], ans - 1LL * pref[j] * pref[j], j}); } Swap(); } cout << ans << "\n"; vector < int > anss; for(int i = m, x = n; x && i >= 1; i--){ x = pr[i][x]; anss.push_back(x); } reverse(anss.begin(), anss.end()); for(auto it : anss){ cout << it << " "; } }
#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...