Submission #890607

#TimeUsernameProblemLanguageResultExecution timeMemory
890607dwuySplit the sequence (APIO14_sequence)C++14
11 / 100
36 ms87112 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; typedef pair<double, double> pdd; typedef pair<int, int> pii; const int MX = 100005; int n, k; int a[MX]; int sum[MX]; int pre[MX]; int cur[MX]; int32_t trace[MX][205]; void nhap(){ cin >> n >> k; for(int i=1; i<=n; i++) cin >> a[i]; } vector<pii> Line; vector<int> id; /// ax + b = ux + v; /// ax - ux = v - b; /// x(a - u) = (v - b) /// x = (v - b)/(a - u); bool bad(pdd l1, pdd l2, pdd l3){ return (l2.se - l1.se)/(l1.fi - l2.fi) >= (l3.se - l2.se)/(l2.fi - l3.fi); } void addLine(pii cur, int idx){ while(Line.size() > 1 && bad(cur, Line.back(), Line[Line.size()-2])){ Line.pop_back(); id.pop_back(); } Line.push_back(cur); id.push_back(idx); } pii get(int x){ int res = (int)Line.size() - 1; for(int lo=0, hi=(int)Line.size()-2; lo<=hi;){ int mid = (lo+hi)>>1; if(x>=1.0*(Line[mid+1].se - Line[mid].se)/(Line[mid].fi - Line[mid+1].fi)) res = mid, hi = mid - 1; else lo = mid + 1; } return {Line[res].fi*x + Line[res].se, id[res]}; } void solve(){ for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i]; for(int i=1; i<=n; i++) pre[i] = sum[i]*(sum[n] - sum[i]); for(int j=2; j<=k; j++){ Line.clear(); id.clear(); addLine({-sum[j-1], pre[j-1]}, j-1); for(int i=j; i<=n; i++){ pii tmp = get(sum[n] - sum[i]); cur[i] = tmp.fi + sum[i]*(sum[n] - sum[i]); trace[i][j] = tmp.se; addLine({-sum[i], pre[i]}, i); } for(int i=1; i<=n; i++) pre[i] = cur[i], cur[i] = 0; } pii ans = {-1, 0}; for(int i=1; i<n; i++) ans = max(ans, {pre[i], i}); vector<int> path; for(int u=ans.se, t=k; u!=0; u=trace[u][t], t--) path.push_back(u); cout << ans.fi << endl; reverse(path.begin(), path.end()); for(int &x: path) cout << x << ' '; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); nhap(); solve(); return 0; }
#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...