Submission #527811

#	Time	Username	Problem	Language	Result	Execution time	Memory
527811		Monarchuwu	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	1 ms	332 KiB

kangaroo

/**
 *  Problem:    CEOI16_kangaroo - Kangaroo
 *  Link:       https://oj.uz/problem/view/CEOI16_kangaroo
 *  Tags:       DP CC
**/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 2000 + 3, mod = 1e9 + 7;
int n, cs, cf;

#define add(a, b) (a += b) %= mod
ll dp[N][N];
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> cs >> cf;
    if (cs > cf) cs = n - cs + 1, cf = n - cf + 1;

    dp[1][1] = 1;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j) if (dp[i - 1][j]) {
            if (cs == i) {
                add(dp[i][j + 1], dp[i - 1][j]); // nhảy sang phải
                add(dp[i][j + 0], dp[i - 1][j]); // nhảy sang trái
                continue;
            }

            if (cf == i) {
                add(dp[i][j + 1], dp[i - 1][j]); // đến từ phải
                add(dp[i][j + 0], dp[i - 1][j]); // đến từ trái
                add(dp[i][j - 1], dp[i - 1][j]); // merge với cs
                continue;
            }

            add(dp[i][j + 1], dp[i - 1][j] * (j - (cs < i) - (cf < i) + 1));
            add(dp[i][j - 1], dp[i - 1][j] * (j - 1));
        }

    cout << dp[n][1] << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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