Submission #33626

#	Time	Username	Problem	Language	Result	Execution time	Memory
33626		dqhungdl	Split the sequence (APIO14_sequence)	C++14	22 / 100	2000 ms	78676 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

int64_t n,k,a[100005],F[205][205][205];
bool Free[205][205][205];
vector<int> rs;

int64_t f(int64_t l,int64_t r,int64_t k)
{
    if(Free[l][r][k]==true)
        return F[l][r][k];
    Free[l][r][k]=true;
    if(k==0)
        return F[l][r][k]=0;
    F[l][r][k]=0;
    int64_t pos;
    for(int64_t i=l;i<r;i++)
        for(int64_t kk=0;kk<k;kk++)
        {
            int64_t tmp=f(l,i,kk)+f(i+1,r,k-kk-1)+(a[i]-a[l-1])*(a[r]-a[i]);
            if(F[l][r][k]<tmp)
            {
                F[l][r][k]=tmp;
                pos=i;
            }
        }
    return F[l][r][k];
}

void Path(int l,int r,int k)
{
    if(k==0)
        return;
    for(int64_t i=l;i<r;i++)
        for(int64_t kk=0;kk<k;kk++)
            if(F[l][r][k]==f(l,i,kk)+f(i+1,r,k-kk-1)+(a[i]-a[l-1])*(a[r]-a[i]))
            {
                rs.push_back(i);
                Path(l,i,kk);
                Path(i+1,r,k-kk-1);
                return;
            }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>k;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    cout<<f(1,n,k)<<"\n";
    Path(1,n,k);
    for(int i=0;i<rs.size();i++)
        cout<<rs[i]<<' ';
}

Compilation message (stderr)

sequence.cpp: In function 'int64_t f(int64_t, int64_t, int64_t)':
sequence.cpp:16:13: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
     int64_t pos;
             ^
sequence.cpp: In function 'int main()':
sequence.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<rs.size();i++)
                  ^

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