Submission #220012

#	Time	Username	Problem	Language	Result	Execution time	Memory
220012		MKopchev	Split the sequence (APIO14_sequence)	C++14	100 / 100	1499 ms	81912 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42,kmax=2e2+5;

long long dp[2][nmax];

int optimal[kmax][nmax];

int n,k;
int inp[nmax];

long long pref[nmax];

long long ask(int l,int r)
{
    return pref[r]-pref[l-1];
}
long long score(int j,int i)
{
    return ask(1,j)*ask(j+1,i);
}

int output[nmax];

int brute(int cuts,int i,int lq,int rq)
{


    int ret=-1;

    dp[cuts&1][i]=-1;

    for(int j=lq;j<=rq&&j<i;j++)
    {
        long long current=dp[(cuts-1)&1][j]+score(j,i);
        if(current>dp[cuts&1][i])
        {
            ret=j;
            dp[cuts&1][i]=current;
        }
    }

    //cout<<"brute "<<cuts<<" "<<i<<" "<<lq<<" "<<rq<<" -> "<<ret<<endl;

    return ret;
}
void dc(int cuts,int l,int r,int lq,int rq)
{
    if(l>r)return;

    rq=min(r,rq);

    int av=(l+r)/2;

    optimal[cuts][av]=brute(cuts,av,lq,rq);

    dc(cuts,l,av-1,lq,optimal[cuts][av]);

    dc(cuts,av+1,r,optimal[cuts][av],rq);
}
int main()
{
    scanf("%i%i",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%i",&inp[i]);
        pref[i]=pref[i-1]+inp[i];
    }

    for(int cuts=1;cuts<=k;cuts++)
    {
        for(int j=0;j<=n;j++)
            dp[cuts%2][j]=-1e18;

        dc(cuts,cuts+1,n,1,n);

        //for(int j=1;j<=n;j++)cout<<optimal[cuts][j]<<" ";cout<<endl;
    }

    printf("%lld\n",dp[k%2][n]);

    int pos=n;
    for(int cuts=k;cuts>=1;cuts--)
    {
        output[cuts]=optimal[cuts][pos];
        pos=optimal[cuts][pos];
    }

    for(int i=1;i<=k;i++)
    {
        printf("%i",output[i]);
        if(i==k)printf("\n");
        else printf(" ");
    }
    return 0;
}

Compilation message (stderr)

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

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