Submission #1225400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225400		MarwenElarbi	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	18 ms	23112 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const int nax=2e3+5;
const int MOD=1e9+7;
long long dp[nax][nax];
int main() {
    int n,l,r;
    cin>>n>>l>>r;
    if(n<=2){
        cout <<0<<endl;
        return 0;
    }
    if(l>r) swap(l,r);
    dp[0][0]=1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= n-i+1; ++j)
        {
           
            if(i<l){
                dp[i][j]+=dp[i-1][j+1]*(j+1)*(j);
                if(j>0) dp[i][j]+=dp[i-1][j-1];
            }else if(i==l){
                dp[i][j]+=dp[i-1][j+1]*(j+1);
                dp[i][j]+= dp[i-1][j];
            }else if(i<r){
                dp[i][j]+=dp[i-1][j+1]*(j+1)*(j+1);
                if(j>0) dp[i][j]+=dp[i-1][j-1];
            }else if(i==r){
                dp[i][j]+=dp[i-1][j+1]*(j+1);
                dp[i][j]+= dp[i-1][j];
            }else{
                dp[i][j]+=dp[i-1][j+1]*(j+2)*(j+1);
                if(j>0) dp[i][j]+=dp[i-1][j-1];
            }
            //if(dp[i][j] > 0)cout << i << " "<<j<<" "<<dp[i][j]<<" "<<dp[i-1][j+1]<<endl;
            dp[i][j]%=MOD;
        }
    } 
    cout <<dp[n-1][0]<<endl;
}

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