Submission #1211845

#TimeUsernameProblemLanguageResultExecution timeMemory
1211845Szymon_PilipczukSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define int long long #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; vector<vector<ll>> l; int n,k; ll sq(ll a) { return a*a; } void add(ll a,ll b,ll ex,ll p,ll i) { ll c = l[p][0],d = l[p][1],e = l[p][2],lp = l[p][3],rp = l[p][4],ci = l[p][7]; if(a * (lp+rp)/2 + b < c * (lp+rp)/2 + d) { l[p][0] = a; l[p][1] = b; l[p][2] = ex; l[p][7] = i; i = ci; a = c; b = d; ex = e; } if(a * lp + b < l[p][0] * lp + l[p][1]) { if(lp <= (lp+rp)/2 -1) { if(l[p][5] != -1) { add(a,b,ex,l[p][5],i); } else { l[p][5] = l.size(); l.pb({a,b,ex,lp,(lp+rp)/2-1,-1,-1,i}); } } } else { if(rp >= (lp+rp)/2 + 1) { if(l[p][6] != -1) { add(a,b,ex,l[p][6],i); } else { l[p][6] = l.size(); l.pb({a,b,ex,(lp+rp)/2+1,rp,-1,-1,i}); } } } } vector<ll> check(ll v,int p) { vector<ll> ans; ans = {l[p][0] * v + l[p][1],l[p][2],l[p][7]}; if((l[p][3]+l[p][4])/2 < v && l[p][6] != -1) { vector<ll> c = check(v,l[p][6]); if(c[0] < ans[0]) { ans = c; } } else if((l[p][3]+l[p][4])/2 > v && l[p][5] != -1) { vector<ll> c = check(v,l[p][5]); if(c[0] < ans[0]) { ans = c; } } return ans; } ll pref[100000]; vector<int> ord; pair<ll,ll> solve(ll c) { l.clear(); ord.clear(); l.pb({0,0,0,0,inf,-1,-1,-1}); vector<vector<ll>> ans(n); rep(i,n) { ans[i] = {check(pref[i],0)[0] + pref[i]*pref[i] + c, check(pref[i],0)[1]+1,check(pref[i],0)[2]}; add(-2 * pref[i],ans[i][0] + pref[i]*pref[i],ans[i][1],0,i); } int i = n-1; while(i != -1) { ord.pb(i); i = ans[i][2]; } ord.pb(-1); return {ans[n-1][0] - c*ans[n-1][1],ans[n-1][1]-1}; } int32_t main() { cin>>n>>k; int cu; cin>>cu; pref[0] = cu; for(int i = 1;i<n;i++) { int c; cin>>c; pref[i] = pref[i-1]+c; } ll l = -1; ll r = 1e18; pair<ll,ll> ans; vector<int> co; while(l+1 < r) { ll mid = (l+r)/2; pair<ll,ll> c = solve(mid); if(c.nd < k) { r = mid; } else if(c.nd >= k) { l = mid; co = ord; ans = c; } } if(l == -1) { ans = solve(-1); co = ord; } ll tans = ans.st + (ans.nd-k)*l; cout<<tans<<"\n"; if(l == -1) { l = 0; } ll cc = (pref[n-1]*pref[n-1]- tans)/2; //cout<<n<<" "<<k<<"\n"; set<int> o; rep(i,co.size()) { o.insert(co[i]); } for(int j = 0;j<n && k < ans.nd;j++) { rep(i,n-1) { if(o.contains(i)) { auto q = o.upper_bound(i); int b = *q; q--;q--; int a = *q; if((a != -1 && sq(pref[b] - pref[a]) - sq(pref[b] - pref[i]) -sq(pref[i] - pref[a]) == l) || (a == -1 && sq(pref[b]) - sq(pref[b] - pref[i]) - sq(pref[i]) == l)) { o.erase(i); ans.nd--; if(k == ans.nd) { break; } } } } } /*ll cc2 = 0; int last = -1; for(int i : o) { if(i!=-1&&i!=n-1) { if(last == -1) { cc2 += pref[i] * (pref[n-1]-pref[i]); } else { cc2+= (pref[i] - pref[last]) * (pref[n-1]-pref[i]); } last = i; } } if(cc2 != cc) return 0;*/ for(int i : o) { if(i != -1 && i != n-1) { cout<<i+1<<" "; } } cout<<"\n"; }
#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...