Submission #1207196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207196		user736482	Split the sequence (APIO14_sequence)	C++20	0 / 100	14 ms	15972 KiB

sequence

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define rev( x ) reverse( x .begin(), x .end())
ll dp[1000007],dppop[1000007];
int pop[1000007][207];
ll n,k,a,b,c,s,s2;
vector<ll>v={0};
deque<pair<pii,ll>>hull;


ll eval(pair<ll,ll>f,ll x){
    return  f.ff*x+f.ss;
}

void add(pair<pair<ll,ll>,ll> pr){
    if(hull.size() && hull.back().ff==pr.ff)return;
    hull.pb(pr);
    while(hull.size()>=3){
        auto p3=hull.back();
        hull.pop_back();
        auto p2=hull.back();
        hull.pop_back();
        auto p1=hull.back();
        ll pom=p3.ff.ss-p1.ff.ss;
        ll pom2=p1.ff.ff-p3.ff.ff;
        if(eval(p2.ff,pom/pom2)>=eval(p1.ff,pom/pom2) && eval(p2.ff,pom/pom2+1)>=eval(p3.ff,pom/pom2+1)){
            hull.pb(p3);
        }
        else{
            hull.pb(p2);hull.pb(p3);break;
        }
    }
}

pii bst(ll x){
    while(hull.size()>=2){
        auto p1=hull.front();
        hull.pop_front();
        auto p2=hull.front();
        if(eval(p1.ff,x)<eval(p2.ff,x)){
            hull.push_front(p1);
            break;
        }
    }
    return {eval(hull.front().ff,x),hull.front().ss};
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    k++;
    for(ll i=0;i<n;i++){
        cin>>a;
        s+=a*a;
        s2+=a;
        v.pb(v.back()+a);
    }
    for(ll i=1;i<=n;i++)dppop[i]=INF;
    for(ll i=1;i<=k;i++){
        if(i==1)
        add({{0,0},0});
        else
        add({{0,INFL},0});
        for(ll j=1;j<=n;j++){
            pii pom=bst(v[j]);
            pom.ff+=v[j]*v[j];
            dp[j]=pom.ff;
            //cout<<dp[j]<<" "<<bst(v[j]).ff<<" "<<bst(v[j]).ss<<" "<<v[j]<<"  ";
            pop[j][i]=pom.ss;
            add({{-2*v[j],dppop[j]+v[j]*v[j]},j});
            //cout<<dppop[j]+v[j]*v[j]<<" "<<-2*v[j]<<"     "<<flush;
        }
        //cout<<"\n"<<flush;
        swap(dp,dppop);
        hull.clear();
    }
    cout<<(s2*s2-dppop[n])/2<<"\n";
    vector<ll> ans;
    ll ak=n;
    while(ak!=0){
        ans.pb(ak);
        ak=pop[ak][k];
        k--;
    }
    rev(ans);
    ans.pop_back();
    for(ll i : ans)cout<<i<<" ";
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29