Submission #604853

#	Time	Username	Problem	Language	Result	Execution time	Memory
604853		nghiass001	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	25 ms	22996 KiB

kangaroo

#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
using namespace std;
const int N = 2005, MOD = 1e9 + 7;
int n, ss, tt;
long long dp[N][N];

int main()
{
    cin >> n >> ss >> tt;
    dp[0][0] = 1;

    int exist = 0;

    FOR(i, 1, n) {
        FOR(j, 0, i) {
            if (i != ss && i != tt) {
                if (i == n) {
                    dp[n][0] = dp[n - 1][1];
                }
                else if (exist == 1) {
                    if (j > 0) dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] += dp[i - 1][j + 1] * j * j;
                }
                else {
                    if (j > 0) dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] += dp[i - 1][j + 1] * (j + 1) * j;
                }
            }
            else {
                if (i == n) {
                    dp[n][0] = dp[n - 1][1];
                }
                if (exist) {
                    if (j > 0) dp[i][j] += dp[i - 1][j];
                    dp[i][j] += dp[i - 1][j + 1] * j;
                }
                else {
                    if (j > 0) dp[i][j] += dp[i - 1][j - 1];
                    dp[i][j] += dp[i - 1][j] * j;
                }
            }
            dp[i][j] %= MOD;
        }
        if (i == ss || i == tt) ++exist;
    }
    cout << dp[n][0];
}

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