Submission #873752

#	Time	Username	Problem	Language	Result	Execution time	Memory
873752		Pannda	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	27 ms	604 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

const int P = (int)1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s, f;
    cin >> n >> s >> f;
    s--;
    f--;

    vector<int> prev(n + 1, 0);
    prev[0] = 1;

    for (int x = 0; x < n; x++) {
        vector<int> dp(n + 1, 0);
        int req = (x > s) + (x > f);
        for (int comp = req; comp <= n; comp++) {
            // create
            if (comp + 1 <= n) {
                if (x == s || x == f) (dp[comp + 1] += prev[comp]) %= P;
                else (dp[comp + 1] += 1LL * (comp + 1 - req) * prev[comp] % P) %= P;
            }

            // merge
            if (comp >= 2 && x != s && x != f) {
                (dp[comp - 1] += 1LL * (comp - 1) * prev[comp] % P) %= P;
            }

            // append, only possible for endpoints
            if (comp >= 1 && (x == s || x == f)) {
                (dp[comp] += prev[comp]) %= P;
            }
        }
        swap(dp, prev);
    }

    cout << prev[1] << '\n';
}

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