Submission #1222014

#TimeUsernameProblemLanguageResultExecution timeMemory
1222014Szymon_PilipczukSplit the sequence (APIO14_sequence)C++20
71 / 100
1393 ms175708 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[201]; int n,k; ll sq(ll a) { return a*a; } /*void add(ll a,ll b,ll p,ll i,int c) { ll d = l[c][p][0],e = l[c][p][1],lp = l[c][p][2],rp = l[c][p][3],ci = l[c][p][6]; if(a * (lp+rp)/2 + b < d * (lp+rp)/2 + e) { l[c][p][0] = a; l[c][p][1] = b; l[c][p][6] = i; i = ci; a = d; b = e; } //cerr<<a<<" "<<b<<" "<<p<<" "<<i<<" "<<c<<" "<<l[c][p][4]<<" "<<l[c][p][5]<<"\n"; if(a * lp + b < l[c][p][0] * lp + l[c][p][1]) { if(lp <= (lp+rp)/2 -1) { if(l[c][p][4] != -1) { add(a,b,l[c][p][4],i,c); } else { l[c][p][4] = l[c].size(); l[c].pb({a,b,lp,(lp+rp)/2,-1,-1,i}); } } } else { if(rp >= (lp+rp)/2 + 1) { if(l[c][p][5] != -1) { add(a,b,l[c][p][5],i,c); } else { l[c][p][5] = l[c].size(); l[c].pb({a,b,(lp+rp)/2+1,rp,-1,-1,i}); } } } } vector<ll> check(ll v,int p,int c) { vector<ll> ans; ans = {l[c][p][0] * v + l[c][p][1],l[c][p][6]}; if((l[c][p][2]+l[c][p][3])/2 < v && l[c][p][5] != -1) { vector<ll> cans = check(v,l[c][p][5],c); if(cans[0] < ans[0]) { ans = cans; } } else if((l[c][p][2]+l[c][p][3])/2 > v && l[c][p][4] != -1) { vector<ll> cans = check(v,l[c][p][4],c); if(cans[0] < ans[0]) { ans = cans; } } return ans; }*/ deque<vector<ll>> dq; void add(ll a,ll b,int i) { if(dq.size() == 0) { dq.push_back({0,infl,a,b,i}); return; } vector<ll> c = dq.back(); if(c[2] == a) { if(c[3] > b) { dq.pop_back(); add(a,b,i); } } else { ll cu = (b-c[3])/(c[2]-a) + 1; if(cu <= c[0]) { dq.pop_back(); add(a,b,i); } else { dq.back()[1] = cu-1; dq.pb({cu,infl,a,b,i}); } } } pair<ll,ll> check(ll c) { if(dq.front()[1] >=c) { return {c * dq.front()[2] + dq.front()[3],dq.front()[4]}; } else { dq.pop_front(); return check(c); } } ll pref[100000]; vector<int> ord; int p[200][99999]; ll solve() { vector<vector<ll>> nx; vector<vector<ll>> nxnx; rep(q,k) { nx = nxnx; nxnx.clear(); dq.clear(); add(0,inf,-1); if(q == 0) { add(0,0,-1); } rep(i,n-1) { //cout<<i<<"\n"; //cerr<<q<<" "<<i<<" "<<ans[q][i].st<<" "<<ans[q][i].nd<<"\n"; p[q][i] = check(pref[i]).nd; nxnx.pb({-2 * pref[i],check(pref[i]).st + pref[i]*pref[i] + pref[i]*pref[i],i}); if(q != 0) add(nx[i][0],nx[i][1],nx[i][2]); //cout<<ans[i][j][0]<<" "<<ans[i][j][1]<<" "<<i<<" "<<j<<"\n"; //cout<<-2*pref[i]<<" "<<ans[i][j][0] +pref[i]*pref[i]<<"\n"; } } //cout<<'a'<<"\n"; dq.clear(); rep(i,n-1) { add(nxnx[i][0],nxnx[i][1],nxnx[i][2]); } int ci = check(pref[n-1]).nd; int cu = k-1; while(ci != -1) { // cout<<ci<<"\n"; ord.pb(ci); ci = p[cu][ci]; cu--; } reverse(all(ord)); return check(pref[n-1]).st + pref[n-1]*pref[n-1]; } int32_t main() { cin>>n>>k; int cu; cin>>cu; pref[0] = cu; rep(i,n-1) { int c; cin>>c; pref[i+1] = pref[i]+c; } ll ans = solve(); //cerr<<ans<<"\n"; cout<<(sq(pref[n-1])-ans)/2<<"\n"; rep(i,k) { cout<<ord[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...