제출 #558089

#제출 시각아이디문제언어결과실행 시간메모리
558089Alexandruabcde캥거루 (CEOI16_kangaroo)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2005;
constexpr int MOD = 1e9 + 7;

int N, cs, cf;
int dp[NMAX][2][NMAX];

void Add (int &x, int y) {
    x = x + y;
    if (x >= MOD) x -= MOD;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> cs >> cf;
    dp[0][0][cs-1] = 1;
    dp[0][1][cs-1] = 1;

    for (int i = 0; i < N-2; ++ i ) {
        for (int cnt_st = 0; cnt_st <= (N-2) - i; ++ cnt_st ) {
            int cnt_dr = (N-2) - i - cnt_st;

            assert(cnt_dr >= 0);

            for (int j = 1; j <= cnt_dr; ++ j )
                Add(dp[i+1][1][cnt_st + (j-1)], dp[i][0][cnt_st]);

            for (int j = 1; j <= cnt_st; ++ j )
                Add(dp[i+1][0][cnt_st-j], dp[i][1][cnt_st]);
        }
    }

    int sol = 0;
    Add(sol, dp[N-2][0][0]);
    Add(sol, dp[N-2][1][0]);

    cout << sol << '\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...