Submission #17617

#	Time	Username	Problem	Language	Result	Execution time	Memory
17617		gs13068	Split the sequence (APIO14_sequence)	C++98	100 / 100	704 ms	93532 KiB

sequence

#include<cstdio>
#include<algorithm>

std::pair<std::pair<int,long long>,int> s[111111];
int sn;

long long a[111111];
long long d[2][111111];
int vi[201][111111];

void insert(int a,long long b,int c)
{
    double t;
    while(sn>=2)
    {
    	if(s[sn-1].first.first==s[sn-2].first.first)t = 0;
        else t = -1.*(s[sn-1].first.second-s[sn-2].first.second)/(s[sn-1].first.first-s[sn-2].first.first);
        if(t*a+b>t*s[sn-1].first.first+s[sn-1].first.second)break;
        sn--;
    }
    s[sn++]=std::make_pair(std::make_pair(a,b),c);
}

void print(int i,int j)
{
    if(i)
    {
        print(i-1,vi[i][j]);
        printf("%d ",vi[i][j]);
    }
}

int main()
{
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
        d[0][i]=a[i]*a[i];
    }
    for(i=1;i<=m;i++)
    {
        k=0;
        sn=0;
        for(j=1;j<=n;j++)
        {
            insert(-2*a[j-1],a[j-1]*a[j-1]+d[!(i&1)][j-1],j-1);
            if(k>=sn)k=sn-1;
            while(k+1<sn)
            {
                if(-(s[k+1].first.second-s[k].first.second)<a[j]*(s[k+1].first.first-s[k].first.first))break;
                k++;
            }
            d[i&1][j]=a[j]*a[j]+s[k].first.first*a[j]+s[k].first.second;
            vi[i][j]=s[k].second;
        }
    }
    printf("%lld\n",(a[n]*a[n]-d[m&1][n])/2);
    print(m,n);
}

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