Submission #1181533

#TimeUsernameProblemLanguageResultExecution timeMemory
1181533meicrisKangaroo (CEOI16_kangaroo)C++17
0 / 100
13 ms31576 KiB
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int N, cs, cf;
int dp[2001][2][2001];
bool visited[2001];
int main() {
    cin >> N >> cs >> cf;
    cs--; cf--;
    memset(dp, 0, sizeof(dp));
    visited[cs] = true;
    for (int i = 0; i < N; i++) {
        if (i == cs) continue;
        if (i < cs) {
            dp[i][0][2] = 1;
        } else {
            dp[i][1][2] = 1;
        }
    }
    for (int k = 2; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int dir = 0; dir <= 1; dir++) {
                if (dp[i][dir][k] == 0) continue;
                for (int j = 0; j < N; j++) {
                    if (j == i) continue;
                    if (dir == 0 && j > i) {
                        if (dp[i][0][k]) {
                            dp[j][1][k + 1] = (dp[j][1][k + 1] + dp[i][0][k]) % MOD;
                        }
                    } else if (dir == 1 && j < i) {
                        if (dp[i][1][k]) {
                            dp[j][0][k + 1] = (dp[j][0][k + 1] + dp[i][1][k]) % MOD;
                        }
                    }
                }
            }
        }
    }
    int result = (dp[cf][0][N] + dp[cf][1][N]) % MOD;
    cout << result << '\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...