Submission #653199

#	Time	Username	Problem	Language	Result	Execution time	Memory
653199		HuyQuang_re_Zero	Split the sequence (APIO14_sequence)	C++14	50 / 100	2099 ms	57524 KiB

sequence

#include <bits/stdc++.h>
#define N 100001
#define db double
using namespace std;
long long n,k,f[N][202],t[N],sum,i,j,a[N],m,tr[N][202];
void truyvet(int i,int j)
{
    if(j==1) return ;
    truyvet(tr[i][j],j-1);
    cout<<tr[i][j]<<" ";
}
int main()
{
  //  freopen("ntu.inp","r",stdin);
  //  freopen("ntu.out","w",stdout);
    cin>>n>>m; m++;
  //  f[0][0]=1;
    //memset(f,-1,sizeof(f));
    for(i=1;i<=n;i++)
    {
        cin>>a[i]; t[i]=t[i-1]+a[i];
        f[i][1]=0;
        for(j=2;j<=min(i,m);j++)
        {
            sum=0; f[i][j]=-1;
            for(k=i;k>=1;k--)
            {
                sum+=a[k];
                if(f[i][j]<f[k-1][j-1]+t[k-1]*sum)
                {
                    f[i][j]=f[k-1][j-1]+t[k-1]*sum;
                    tr[i][j]=k-1;
                }
            //    if(i==2 && j==2 && k==1) cerr<<sum<<" "<<t[k-1]<<'\n';
              //  if(i==5 && j==2 && f[i][j]==48) cerr<<k<<" "<<f[k-1][j-1]<<'\n';
            }
        }
    }
    //cerr<<f[4][1]<<'\n';
    cout<<f[n][m]<<'\n';
    truyvet(n,m);
}

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