Submission #741038

#	Time	Username	Problem	Language	Result	Execution time	Memory
741038		FEDIKUS	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	43 ms	31692 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll maxn=2010;
const ll mod=1e9+7;

ll dp[maxn][maxn];

int main(){
    //freopen("kangaroo.in","r",stdin);
    ll n,s,f;
    cin>>n>>s>>f;
    dp[0][0]=1;
    for(ll i=1;i<=n;i++){
        if(i==s || i==f){
            for(ll j=1;j<=n;j++){
                dp[i][j]+=dp[i-1][j-1];
                dp[i][j]+=dp[i-1][j];
                dp[i][j]%=mod;
            }
        }else{
            for(ll j=1;j<=n;j++){
                dp[i][j]+=j*dp[i-1][j+1]%mod;
                dp[i][j]%=mod;
                dp[i][j]+=(j-ll(i>s)-ll(i>f))*dp[i-1][j-1];
                dp[i][j]%=mod;
            }
        }
        //cout<<i<<": ";
        //for(ll j=1;j<=n;j++) cout<<dp[i][j]<<" "; cout<<"\n";
    }
    //freopen("kangaroo.out","w",stdout);
    cout<<dp[n][1];
    return 0;
}

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