Submission #17670

#	Time	Username	Problem	Language	Result	Execution time	Memory
17670		Namnamseo	Split the sequence (APIO14_sequence)	C++14	100 / 100	692 ms	85076 KiB

sequence

#include <cstdio>
typedef long long ll;

int n,k;
int d[100010];

ll prefix[100010];

ll dp[2][100010];
ll *dp_bef, *dp_cur;

int chosen[201][100010];
int* chosen_arr;

struct tp{
    ll a,b,c;
    tp cross(const tp& other) const {
        return {b*other.c-c*other.b, c*other.a-a*other.c, a*other.b-b*other.a};
    }
} l[100010];
int lind[100010];
int ln;

void addLine(ll a,ll c,int ind){
    tp curl={a,-1,c};
    tp pa, pb;
    while(ln>=2){
        pa=l[ln-2].cross(l[ln-1]);
        pb=l[ln-1].cross(curl);
        if(pa.a*pb.c < pa.c*pb.a) break;
        --ln;
    }
    l   [ln]=curl;
    lind[ln]=ind;
    ++ln;
}

void work(int trial){
    int i;
    ln=0;
    addLine(0,0,0);
    int lli=0;
    for(i=1; i<=n; ++i){
        while(lli+1<ln){
            tp cp=l[lli].cross(l[lli+1]);
            if(cp.a <= cp.c * prefix[i]) ++lli;
            else break;
        }
        dp_cur[i] = l[lli].a*prefix[i] + l[lli].c;
        chosen[trial][i]=lind[lli];
        addLine(prefix[i], dp_bef[i]-prefix[i]*prefix[i], i);
    }
}

int ans[201];

int main()
{
    scanf("%d%d",&n,&k);// ++k;
    int i;
    for(i=1;i<=n;++i) scanf("%d",d+i), prefix[i]=prefix[i-1]+d[i];
    dp_bef=dp[0], dp_cur=dp[1];
    for(i=1;i<=k;++i){
        chosen_arr=chosen[i];
        work(i);
        auto tmp=dp_cur; dp_cur=dp_bef; dp_bef=tmp;
    }
    printf("%lld\n",dp_bef[n]);
    int j;
    i=k; j=n;
    while(true){
        ans[i]=j;
        if(i==0) break;
        j=chosen[i--][j];
    }
    for(i=0; i<k; ++i) printf("%d ",ans[i]);
    return 0;
}

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