Submission #1181533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181533		meicris	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	13 ms	31576 KiB

kangaroo

#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;
}

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