Submission #551335

#	Time	Username	Problem	Language	Result	Execution time	Memory
551335		ToroTN	Split the sequence (APIO14_sequence)	C++14	0 / 100	894 ms	131072 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,a[100005],dp[100005][205],qs[200005],sum[200005],track[100005][205],u,step;
ll query(ll l,ll r)
{
    return (sum[r]-sum[l-1])*(sum[r]-sum[l-1])-(qs[r]-qs[l-1]);
}
stack<long long> stk;
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],qs[i]=qs[i-1]+a[i]*a[i];
    /*for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            printf("%d %d %lld\n",i,j,query(i,j));
        }
    }*/
    for(int i=0;i<=n;i++)for(int j=0;j<=m+1;j++)dp[i][j]=2e18;
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m+1;j++)
        {
            for(int k=0;k<i;k++)
            {
                if(dp[k][j-1]+query(k+1,i)<=dp[i][j])
                {
                    dp[i][j]=dp[k][j-1]+query(k+1,i);
                    track[i][j]=k;
                }
            }
        }
    }
    u=n;
    step=m+1;
    while(u>=0)
    {
        if(u==0)
        {
            break;
        }
        if(u!=n)stk.push(u);
        u=track[u][step];
        --step;
    }
    printf("%lld\n",(long long)stk.size());
    while(!stk.empty())
    {
        printf("%lld ",stk.top());
        stk.pop();
    }
    printf("\n");
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:13:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i],qs[i]=qs[i-1]+a[i]*a[i];
      |                          ~~~~~^~~~~~~~~~~~~~

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