Submission #963011

#	Time	Username	Problem	Language	Result	Execution time	Memory
963011		Ghetto	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	0 ms	348 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 2e3 + 5;
const lint MOD = 1e9 + 7;

int n;
int s, f;

lint mod(lint x) {
    return x % MOD;
}

lint dp[MAX_N][MAX_N];
void do_dp() {
    dp[1][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int c = 1; c <= n; c++) {
            // cout << i << ", " << c << ": " << dp[i][c] << endl;

            if ((i + 1) == s || (i + 1) == f) {
                dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + dp[i][c]);
                dp[i + 1][c] = mod(dp[i + 1][c] + dp[i][c]);
                continue;
            }

            lint mult = c + 1;
            mult -= (bool) (i > s);
            mult -= (bool) (i > f);
            
            dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + mod(dp[i][c] * mult));
            dp[i + 1][c - 1] = mod(dp[i + 1][c - 1] + mod(dp[i][c] * (c - 1)));
        }
    }
}

int main() {
    // freopen("kangaroo.in", "r", stdin);

    cin >> n >> s >> f;
    if (s > f) swap(s, f);

    do_dp();
    cout << dp[n][1] << '\n';
}

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