Submission #194125

#	Time	Username	Problem	Language	Result	Execution time	Memory
194125		toma	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	115 ms	31992 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;
 
int N, S, T;
lint memo[2005][2005];
 
lint dp(int n, int comp) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N - 1) { 
        return comp == 0; // use last piece to merge S and T component
    }
    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); // mege with free component
    } else {
        res += dp(n + 1, comp + 1); // add new component
        res += comp * (comp - 1) * dp(n + 1, comp - 1); // merge two free components
        if (n > S) { // merge start with free
            res += comp * dp(n + 1, comp - 1); // append S to a component, and it cannot be modified further
        }
        if (n > T) { // merge end with free
            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: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49