Submission #631586

#	Time	Username	Problem	Language	Result	Execution time	Memory
631586		bachhoangxuan	Split the sequence (APIO14_sequence)	C++17	100 / 100	802 ms	89592 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
#define maxk 205
#define pii pair<int,int>
const ll inf=LLONG_MAX;
int trace[maxn][maxk];
struct line{
    ll a,b,p;
    int id;
    bool operator<(line l){return a<l.a;}
    bool operator<(ll k){return p<k;}
};
struct cvht{
    line x[maxn];
    ll res[maxn];
    int pos=0,sz=0;
    ll div(ll a,ll b){
        return a/b-((a^b)<0 && a%b);
    }
    bool isect(line &l,line &y){
        if(l.a==y.a) l.p=(l.b>y.b)?inf:-inf;
        else l.p=div(y.b-l.b,l.a-y.a);
        return l.p>=y.p;
    }
    void add(line l){
        if(sz!=0) isect(x[sz],l);
        while(sz>=2 && x[sz-1].p>=x[sz].p){
            sz--;
            isect(x[sz],l);
        }
        x[++sz]=l;
    }
    ll query(ll &v,int &i,int &j){
        pos=lower_bound(x+1,x+sz+1,v)-x;
        trace[i][j]=x[pos].id;
        return x[pos].a*v+x[pos].b;
    }
}dp[2];
int n,k,t=0;
ll x[maxn];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> k;
    for(int i=1;i<=n;i++){cin >> x[i];x[i]+=x[i-1];}
    for(int i=1;i<=k;i++){
        t^=1;dp[t^1].sz=0;
        dp[t^1].add({x[i],dp[t^1].res[i]-x[i]*x[i],inf,i});
        for(int j=i+1;j<=n;j++){
            dp[t].res[j]=dp[t^1].query(x[j],j,i);
            dp[t^1].add({x[j],dp[t^1].res[j]-x[j]*x[j],inf,j});
        }
    }
    int c=n,d=k;
    cout << dp[t].res[n] << '\n';
    while(trace[c][d]!=0){
        cout << trace[c][d] << ' ';
        c=trace[c][d];d--;
    }
}

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