Submission #194263

#	Time	Username	Problem	Language	Result	Execution time	Memory
194263		rama_pang	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	232 ms	126428 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][2][2];

lint dp(int n, int comp, int lend, int rend) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N - 1) { 
        return comp == 0 ? 1 : 0; // use last piece to merge S and T component
    }

    lint &res = memo[n][comp][lend][rend];
    if (res != -1) {
        return res;
    }
    
    res = 0;

    if (n == S) {
        res += dp(n + 1, comp, 1, rend); // make new component
        res += dp(n + 1, comp - 1, 1, rend) * comp; // connect a component to left end
    } else if (n == T) {
        res += dp(n + 1, comp, lend, 1); // make new component
        res += dp(n + 1, comp - 1, lend, 1) * comp; // connect a component to right end
    } else {
        res += dp(n + 1, comp + 1, lend, rend); // add a new component
        res += dp(n + 1, comp - 1, lend, rend) * comp * (comp - 1); // merge two components
        res += dp(n + 1, comp - 1, lend, rend) * comp * lend; // connect component to left end
        res += dp(n + 1, comp - 1, lend, rend) * comp * rend; // connect component to right end
    }

    res %= MOD;
    return res;
}

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

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