Submission #1294101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294101		dragonrobot	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	29 ms	31804 KiB

kangaroo

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

#define ll long long

const ll MOD = 1000000007;

ll addmod(ll a, ll b){ 
    a += b; 
    if(a >= MOD) a -= MOD; 
    return a; 
}

ll mulmod(ll a, ll b){ 
    return (a * b) % MOD; 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, s, t;
    if(!(cin >> n >> s >> t)) return 0;

    vector<vector<ll>> f(n+2, vector<ll>(n+3, 0));
    f[1][1] = 1;

    for(int i = 2; i <= n; ++i){
        if(i != s && i != t){
            for(int j = 1; j <= n; ++j){
                ll avail = j - (i > s) - (i > t); // replaced int with ll
                if(avail > 0){
                    f[i][j] = addmod(f[i][j], mulmod(f[i-1][j-1], avail));
                }
                if(j+1 <= n){
                    f[i][j] = addmod(f[i][j], mulmod(f[i-1][j+1], j));
                }
            }
        } else {
            for(int j = 1; j <= n; ++j){
                f[i][j] = addmod(f[i][j], f[i-1][j-1]);
                f[i][j] = addmod(f[i][j], f[i-1][j]);
            }
        }
    }

    cout << f[n][1] % MOD << '\n';
    return 0;
}

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