Submission #1143902

#TimeUsernameProblemLanguageResultExecution timeMemory
1143902imarnSplit the sequence (APIO14_sequence)C++20
100 / 100
959 ms81548 KiB
#include<bits/stdc++.h> #define f first #define s second #define ll long long #define pb push_back #define pii pair<int,int> #define pll pair<ll,ll> #define sz(x) (int)x.size() using namespace std; const int mxn=2e5+5; ll a[mxn]{0}; ll dpf[mxn]{0},dps[mxn]{0}; int pr[202][mxn]{0}; int cur=1,n; void solve(int l,int r,int opl,int opr){ if(l>r)return; int m=(l+r)>>1; pll t={-1e16,-1e16}; for(int i=opl;i<=min(m-1,opr);i++){ t=max(t,{dpf[i]+(a[n]-a[m])*(a[m]-a[i]),i}); }dps[m]=t.f;pr[cur][m]=t.s; if(l==r)return; solve(l,m-1,opl,t.s); solve(m+1,r,t.s,opr); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int k;cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1]; for(int i=1;i<=n;i++)dpf[i]=(a[i])*(a[n]-a[i]); for(int i=2;i<=k;i++){ solve(i,n,i-1,n); for(int j=1;j<=n;j++)dpf[j]=dps[j]; cur++; }ll ans=-1,mem=-1; for(int i=1;i<=n;i++){ if(dpf[i]>ans){ ans=dpf[i]; mem=i; } } cout<<ans<<'\n';stack<int>st;st.push(mem); for(int i=cur-1;i>=1;i--){ st.push(pr[i][mem]);mem=pr[i][mem]; }while(!st.empty()){ cout<<st.top()<<' ';st.pop(); } }
#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...