Submission #18280

#	Time	Username	Problem	Language	Result	Execution time	Memory
18280		mindol	Split the sequence (APIO14_sequence)	C++98	100 / 100	620 ms	84784 KiB

sequence

#include<cstdio>
#include<stack>
using namespace std;
long long S[100001];
long long dt[2][100001];
int sel[201][100001];
stack<int> st;
struct Elem{long long a,b; int index;};
    Elem data[100010];
    int s,e;
double crossX(long long pa,long long pb,long long qa,long long qb){ return ((double)qb-pb)/((double)pa-qa); }
void add(long long a,long long b,int index)
{
    if(s!=e)
    {
        if(data[e-1].a==a)
        {
            if(data[e-1].b<b) data[e-1]={a,b,index};
            return;
        }
    }
    while(e-s>=2)
    {
        if(crossX(data[e-2].a,data[e-2].b,data[e-1].a,data[e-1].b)>=crossX(data[e-1].a,data[e-1].b,a,b))
            e--;
        else break;
    }
    data[e++]={a,b,index};
}
void get_min(long long x)
{
    while(e-s>=2)
    {
        if(data[s].a*x+data[s].b<data[s+1].a*x+data[s+1].b)
            s++;
        else break;
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    int N,K;
    scanf("%d %d",&N,&K);
    for(int i=1,x;i<=N;i++)
        scanf("%d",&x),S[i]=S[i-1]+x;
    for(int i=2;i<=K+1;++i)
    {
        s=e=0;
        add(S[i-1],dt[(i-1)&1][i-1]-S[i-1]*S[i-1],i-1);
        for(int j=i;j<=N;++j)
        {
            get_min(S[j]);
            dt[i&1][j]=data[s].a*S[j]+data[s].b;
            sel[i][j]=data[s].index;
            add(S[j],dt[(i-1)&1][j]-S[j]*S[j],j);
        }
    }
    printf("%lld\n",dt[(K+1)&1][N]);
    int now_i=K+1,now_j=sel[K+1][N];
    while(now_i!=1)
    {
        st.push(now_j);
        now_i--; now_j=sel[now_i][now_j];
    }
    while(!st.empty()) printf("%d ",st.top()),st.pop();
    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