Submission #1150397

#TimeUsernameProblemLanguageResultExecution timeMemory
1150397sitablechairSplit the sequence (APIO14_sequence)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define m first #define n second #define pb push_back #define all(x) x.begin(),x.end() #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define F "TASK" #define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout); #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=2e5+3; typedef pair<ll,ll> ln; vector<ln> vt; vector<int> idx; long double inter(ln a,ln b) { assert(a.m!=b.m); return (long double)(b.n-a.n)/((long double)(a.m-b.m)); } bool bad(ln a,ln b,ln c) { if (b.m==c.m) return (b.n>c.n); return inter(a,c)>=inter(b,c); } pair<ll,int> query(ll x) { if (sz(vt)==0) return {-1e17,69}; int l=0,r=sz(vt)-1; while(l<r) { int mid=l+(r-l+1)/2; if (mid==0) l=mid; else { if (inter(vt[mid],vt[mid-1])>=x) l=mid; else r=mid-1; } } return {vt[l].m*x+vt[l].n,idx[l]}; } void insert(ll x,ll y,int id) { if (sz(vt) && vt.back().m==x && vt.back().n>=y) return; while(sz(vt)>=2 && bad(vt[sz(vt)-2],vt.back(),{x,y})) vt.pop_back(),idx.pop_back(); while(sz(vt) && vt.back().m==x) vt.pop_back(),idx.pop_back(); vt.pb({x,y}); idx.pb(id); } ll dp[202][N],pf[N],ans=0; int opt[202][N]; int n,k,a[N]; vector<int> track; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; For(i,1,n) { cin >> a[i]; pf[i]=pf[i-1]+a[i]; } pair<int,int> cur={0,0}; For(j,1,k) { vt.clear(); idx.clear(); insert(-pf[j-1],dp[j-1][j-1],j-1); For(i,j,n-1) { auto res=query(pf[n]-pf[i]); dp[j][i]=pf[i]*(pf[n]-pf[i])+res.m; opt[j][i]=res.n; insert(-pf[i],dp[j-1][i],i); } For(i,1,n-1) if (dp[j][i]>ans) { ans=dp[j][i]; cur={j,i}; } } cout << ans << endl; while(cur.m>0) { track.pb(cur.n); cur={cur.m-1,opt[cur.m][cur.n]}; } reverse(all(track)); for(auto el: track) cout << el << " "; 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...