Submission #220002

#	Time	Username	Problem	Language	Result	Execution time	Memory
220002		MKopchev	Split the sequence (APIO14_sequence)	C++14	50 / 100	2090 ms	3176 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42,kmax=2e2+5;
long long dp[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 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 i=1;i<=n;i++)
        {
            if(i<cuts){dp[cuts][i]=-1e18;continue;}
            for(int j=cuts-1;j<i;j++)
                dp[cuts][i]=max(dp[cuts][i],dp[cuts-1][j]+score(j,i));
        }

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

    int pos=n;
    for(int cuts=k;cuts>=1;cuts--)
    {
        for(int j=pos-1;j>=1;j--)
            if(dp[cuts][pos]==dp[cuts-1][j]+score(j,pos))
            {
                output[cuts]=j;
                pos=j;
                break;
            }
    }

    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:24: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:27: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: 0 / 21
• Subtask 6: 0 / 29