제출 #376649

#제출 시각아이디문제언어결과실행 시간메모리
376649thiago4532캥거루 (CEOI16_kangaroo)C++17
100 / 100
52 ms32108 KiB
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxn = 2010;
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int n;
int ini, fim;

int solve(int i, int k) {
    if (i == n+1) return (k==1);
    if (dp[i][k] != -1) return dp[i][k];

    int caso1, caso2;
    if (i == ini || i == fim) {
        caso1 = solve(i+1, k+1);
        caso2 = k > 0 ? solve(i+1, k) : 0;
    } else if (i < ini && i < fim) {
        caso1 = (k+1) * solve(i+1, k+1);
        caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
    } else if (i < ini || i < fim) {
        caso1 = k * solve(i+1, k+1);
        caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
    } else {
        caso1 = (k-1) * solve(i+1, k+1);
        caso2 = k > 1 ? (k-1) * solve(i+1, k-1) : 0;
    }
    return dp[i][k] = (caso1 + caso2) % mod;
}

int32_t main() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    cin >> ini >> fim;
    cout << solve(1, 0) << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...