Submission #554293

#	Time	Username	Problem	Language	Result	Execution time	Memory
554293		hibiki	Kangaroo (CEOI16_kangaroo)	C++11	100 / 100	53 ms	32372 KiB

kangaroo

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

#define MOD 1000000007

int n,s,t;
long dp[2020][2020];

long solve(int lv,int g)
{
    if(lv==0)return 0;
    long &now = dp[lv][g];
    if(now!=-1)return now;
    if(lv==1)return now=(g==1?1:0);
    if(lv==s||lv==t)
        return now=(solve(lv-1,g-1)+solve(lv-1,g))%MOD;
    return now=(solve(lv-1,g+1)*g + solve(lv-1,g-1)*(g-(lv>s?1:0)-(lv>t?1:0)))%MOD;
}

main()
{
    // freopen("kangaroo.in","r",stdin);
    // freopen("kangaroo.out","w",stdout);
    memset(dp,-1,sizeof(dp));
    scanf("%d %d %d",&n,&s,&t);
    printf("%ld\n",solve(n,1));
}

Compilation message (stderr)

kangaroo.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main()
      | ^~~~
kangaroo.cpp: In function 'int main()':
kangaroo.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %d",&n,&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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