제출 #1001512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001512		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	6 / 100	0 ms	2396 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
int dp[2010][2010],M=1e9+7;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,a,b;
    cin>>n>>a>>b;
    dp[0][0]=1;
    if(a>b)swap(a,b);
    for(int i=1;i<a;i++) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])*j%M;
    for(int j=1;j<=a;j++)
        dp[a][j]=(dp[a-1][j-1]+dp[a-1][j])%M;
    for(int i=a;++i<b;) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]*(j-1)+dp[i-1][j+1]*j)%M;
    for(int j=1;j<=a;j++)
        dp[b][j]=(dp[b-1][j-1]+dp[b-1][j])%M;
    for(int i=b;i++<n;) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]*max(0,j-2)+dp[i-1][j+1]*j)%M;
    cout<<dp[n][1]<<'\n';
}

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