Submission #194102

#	Time	Username	Problem	Language	Result	Execution time	Memory
194102		rama_pang	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	31 ms	31864 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1000000007;

int N, S, T;
lint memo[2005][2005];

lint dp(int n, int comp) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N) { 
        return comp == 0;
    }
    if (memo[n][comp] != -1) {
        return memo[n][comp];
    }

    lint &res = memo[n][comp] = 0;

    if (n == S || n == T) {
        res += dp(n + 1, comp); // add S or T as new component
        res += comp * dp(n + 1, comp - 1); // add S or T as beginning / end. After that we cannot modify it anymore, so ignore it (AKA delete it).
    } else {
        res += dp(n + 1, comp + 1); // add new component
        res += comp * (comp - 1) * dp(n + 1, comp - 1); // join two components
        if (n > S) {
            res += comp * dp(n + 1, comp - 1); // append S to a component, and it cannot be modified further
        }
        if (n > T) {
            res += comp * dp(n + 1, comp - 1); // append T to a component, and it cannot be modified further
        }
    }

    res %= MOD;
    return res;
}

int main() {
    memset(memo, -1, sizeof(memo));
    cin >> N >> S >> T;
    S--, T--;
    cout << dp(0, 0) << "\n";
    return 0;
}

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