Submission #231111

#	Time	Username	Problem	Language	Result	Execution time	Memory
231111		MKopchev	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	62 ms	16792 KiB

kangaroo

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

const int nmax=2e3+42,mod=1e9+7;

int dp[nmax][nmax];

int n,beg,en;

int rec(int to_place,int groups)
{
    if(to_place>n)return groups==1;

    if(dp[to_place][groups]!=-1)return dp[to_place][groups];

    long long ret=0;
    if(to_place==beg||to_place==en)
    {
        ret=rec(to_place+1,groups);//place with the first/last group
        ret+=rec(to_place+1,groups+1);//make new group
    }
    else
    {
        ret=1LL*(groups-1)*rec(to_place+1,groups-1);//merge 2 groups

        int positions=groups+1;

        if(to_place>beg)positions--;

        if(to_place>en)positions--;

        if(positions>0)ret+=1LL*positions*rec(to_place+1,groups+1);//create new group

    }


    ret=ret%mod;
    dp[to_place][groups]=ret;
    return ret;
}
int main()
{
    scanf("%i%i%i",&n,&beg,&en);

    memset(dp,-1,sizeof(dp));

    printf("%i\n",rec(1,0));
    return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&beg,&en);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49