Submission #1268316

#TimeUsernameProblemLanguageResultExecution timeMemory
1268316WH8Split the sequence (APIO14_sequence)C++20
50 / 100
665 ms196608 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<int, int> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' struct Line { mutable long long k, m, p; // slope, intercept, last x where this line is best int id; // label/index bool operator<(const Line& o) const { return k < o.k; } bool operator<(long long x) const { return p < x; } // for lower_bound(x) }; struct LineContainer : std::multiset<Line, std::less<>> { static const long long INF = (1LL<<62); static long long floordiv(long long a, long long b) { long long q = a / b, r = a % b; if (r && ((a ^ b) < 0)) --q; return q; } // sets x->p = last x where x is >= y; returns true if x->p >= y->p (y is useless) bool isect(iterator x, iterator y) { if (y == end()) { x->p = INF; return false; } if (x->k == y->k) { // same slope: keep the better intercept; if equal, keep higher id if (x->m > y->m || (x->m == y->m && x->id > y->id)) x->p = INF; else x->p = -INF; } else { // last integer x where x is better than y x->p = floordiv(y->m - x->m, x->k - y->k); } return x->p >= y->p; } // Before inserting, kill worse equal-slope neighbors (keep larger m, tie -> higher id) void add(long long k, long long m, int id) { Line L{ k, m, 0, id }; // Remove dominated equal-slope line if present auto it = lower_bound(k); // first with slope >= k if (it != end() && it->k == k) { if (it->m > m || (it->m == m && it->id >= id)) return; // existing is better it = erase(it); // new one is >=, so remove old } else if (it != begin()) { auto it2 = std::prev(it); if (it2->k == k) { if (it2->m > m || (it2->m == m && it2->id >= id)) return; erase(it2); } } auto z = insert(L), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } // Query max at x; if tie on value, prefer higher id. std::pair<int,long long> query(long long x) const { assert(!empty()); auto it = lower_bound(x); // best candidate by breakpoints long long bestVal = it->k * x + it->m; int bestId = it->id; // Tie-break check with neighbors: only adjacent lines can tie at a point. // Check predecessor if (it != begin()) { auto pr = std::prev(it); long long v = pr->k * x + pr->m; if (v == bestVal && pr->id > bestId) { bestId = pr->id; // bestVal unchanged } } // Check successor auto nx = std::next(it); if (nx != end()) { long long v = nx->k * x + nx->m; if (v == bestVal && nx->id > bestId) { bestId = nx->id; } } return {bestId, bestVal}; } }; // to use: // LineContainer hull; // hull.add(m, c); // hull.query(x); // to convert max queries to min queries: // hull.add(-m, -c); // -hull.query(x); LineContainer hull[205]; int n,k; signed main(){ cin>>n>>k; vector<int> v(n+1,0), p(n+1, 0); for(int i=1;i<=n;i++){ cin>>v[i]; p[i]=p[i-1]+v[i]; } vector<vector<int>> dp(n+1, vector<int>(k+1, 0)); vector<vector<pair<int,int>>> from(n+1, vector<pair<int,int>>(k+1)); for(int m=0;m<=k;m++){ hull[m].add(0, 0, 0); } int ans=LLONG_MIN,a=0,b=0; for(int i=1;i<=n;i++){ for(int m=k;m>=1;m--){ auto [id, best]=hull[m-1].query(p[i]); int add=-p[i]*p[i]+p[i]*p[n]; dp[i][m]=best+add; from[i][m]={id, m-1}; if(dp[i][m] > ans){ ans=dp[i][m]; a=i,b=m; } hull[m].add(p[i], dp[i][m]-p[i]*p[n], i); //~ printf("i:%lld, splits:%lld, best %lld add %lld\n",i,m,best,add); //~ printf("added m=%lld, c=%lld\n", p[i], dp[i][m]-p[i]*p[n]); } } cout<<ans<<'\n'; int ca=a, cb=b,cnt=0; while(ca>0 and cb>0){ cnt++; tie(ca,cb)=from[ca][cb]; } assert(cnt==k); while(a>0 and b>0){ cout<<a<<" "; tie(a,b)=from[a][b]; } } /* 4 2 3 1 2 3 */
#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...