Submission #1183713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183713		meicris	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	324 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int N, cs, cf;
vector<vector<vector<int>>> dp;
int solve(int current, int prev, int mask) {
    if (mask == (1 << N) - 1) {
        return current == cf ? 1 : 0;
    }
    int &res = dp[current][prev][mask];
    if (res != -1) return res;
    res = 0;
    for (int next = 0; next < N; ++next) {
        if (mask & (1 << next)) continue;
        if ((prev < current && next < current) || (prev > current && next > current)) {
            res = (res + solve(next, current, mask | (1 << next))) % MOD;
        }
    }
    return res;
}
int main() {
    cin >> N >> cs >> cf;
    cs--; cf--;
    if (N > 20) {
        return 0;
    }
    dp.assign(N, vector<vector<int>>(N, vector<int>(1 << N, -1)));
    int ans = 0;
    for (int next = 0; next < N; ++next) {
        if (next == cs) continue;
        ans = (ans + solve(next, cs, (1 << cs) | (1 << next))) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

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