Submission #56011

#	Time	Username	Problem	Language	Result	Execution time	Memory
56011		ansol4328	Split the sequence (APIO14_sequence)	C++98	50 / 100	1259 ms	87668 KiB

sequence

#include<stdio.h>
#include<memory.h>
#define MAXN 100000

typedef long long ll;

double get_point(ll a1, ll b1, ll a2, ll b2)
{
    if(a1==a2) return 0;
    return (double)(b2-b1)/(a1-a2);
}

struct cht
{
    ll a[MAXN+2], b[MAXN+2];
    int cnt, c[MAXN+2], before;
    double point[MAXN+2];
    void clr()
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(point,0,sizeof(point));
        before=0;
        cnt=0;
    }
    void push(ll a1, ll b1, ll i)
    {
        if(a1==a[cnt] && cnt!=0) return;
        cnt++;
        a[cnt]=a1, b[cnt]=b1, c[cnt]=i;
        if(cnt==1) point[cnt]=0;
        else point[cnt]=get_point(a[cnt-1],b[cnt-1],a[cnt],b[cnt]);
        if(cnt>1)
        {
            while(cnt>1 && point[cnt-1]>=point[cnt])
            {
                a[cnt-1]=a[cnt];
                b[cnt-1]=b[cnt];
                c[cnt-1]=c[cnt];
                a[cnt]=b[cnt]=c[cnt]=point[cnt]=0;
                cnt--;
                point[cnt]=get_point(a[cnt-1],b[cnt-1],a[cnt],b[cnt]);
            }
        }
    }
    ll get_value(double x)
    {
        int st=1, fn=cnt, mid;
        int idx=-1;
        while(st<=fn)
        {
            mid=(st+fn)/2;
            if(point[mid]<=x) idx=mid, st=mid+1;
            else fn=mid-1;
        }
        before=c[idx];
        return a[idx]*x+b[idx];
    }
};

int n, k;
ll m[MAXN+2], s[MAXN+2], q[2][MAXN+2][2], dp[MAXN+2];
int path[202][MAXN+2], res[205];
cht lst;

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1 ; i<=n ; i++)
    {
        scanf("%lld",&m[i]);
        s[i]=s[i-1]+m[i];
    }
    for(int i=0 ; i<=k ; i++)
    {
        int ib1=(i-1)%2, ib2=i%2;
        lst.clr();
        if(i==0)
        {
            for(int j=1 ; j<=n ; j++) q[ib2][j][0]=s[j], q[ib2][j][1]=-s[j]*s[j];
            continue;
        }
        for(int j=i+1 ; j<=n ; j++)
        {
            lst.push(q[ib1][j-1][0],q[ib1][j-1][1],j-1);
            dp[j]=lst.get_value(s[j]);
            q[ib2][j][0]=s[j], q[ib2][j][1]=dp[j]-s[j]*s[j];
            path[i][j]=lst.before;
        }
    }
    printf("%lld\n",dp[n]);
    int i=n, k2=k;
    while(k2!=0)
    {
        i=path[k2][i];
        res[k2]=i;
        k2--;
    }
    for(int i=1 ; i<=k ; i++) printf("%d ",res[i]);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&m[i]);
         ~~~~~^~~~~~~~~~~~~~

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