Submission #1330088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330088		anarch_y	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	23 ms	23020 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#define int long long

const int mod = 1e9+7;
int dp[2001][2001];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, s, f; cin >> n >> s >> f;
    int m = 0;
    dp[1][1] = 1;
    if(s == 1 or f == 1){
        m = 1;
    }
    for(int i=2; i<=n; i++){
        for(int j=1; j<=i; j++){
            if(i != s and i != f){
                dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= mod;
                if(m <= 1){
                    dp[i][j] += ((j+1-m)*j*dp[i-1][j+1])%mod;
                    dp[i][j] %= mod;
                }
                else{
                    if(i == n and j == 1){
                        dp[i][j] += dp[i-1][j+1];
                        dp[i][j] %= mod;
                    }
                    else if(j >= 2){
                        dp[i][j] += (j*(j-1)*dp[i-1][j+1])%mod;
                        dp[i][j] %= mod;
                    }
                }
            }
            else{
                dp[i][j] += dp[i-1][j-1];
                dp[i][j] %= mod;
                if(m == 0){
                    dp[i][j] += (j*dp[i-1][j])%mod;
                    dp[i][j] %= mod;
                }
                else{
                    if(i == n and j == 1){
                        dp[i][j] += dp[i-1][j];
                        dp[i][j] %= mod;
                    }
                    else if(j >= 2){
                        dp[i][j] += ((j-1)*dp[i-1][j])%mod;
                        dp[i][j] %= mod;
                    }
                }
            }
        }
        if(i == s or i == f){
            m++;
        }
    }
    cout << dp[n][1];
}

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