제출 #613907

#제출 시각아이디문제언어결과실행 시간메모리
613907lorenzoferrariKangaroo (CEOI16_kangaroo)C++17
0 / 100
23 ms62884 KiB
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr int N = 200;
constexpr int mod = 1e9 + 7;

int dp[2][N][N][N];

int solve(int w, int a, int b, int c) {
    if (dp[w][a][b][c] != -1) return dp[w][a][b][c];
    LL cur = 0;
    if (w == 0) {
        for (int k = 0; k < b; ++k) cur += solve(1, c, b-1-k, a+k);
        for (int k = 0; k < c; ++k) cur += solve(0, c-1-k, k, a+b);
    } else {
        for (int k = 0; k < c; ++k) cur += solve(0, c-1-k, k, a+b);
    }
    cur %= mod;
    return dp[w][a][b][c] = cur;
}

int main() {
    for (int a = 0;a < N; ++a) for (int b = 0; b < N; ++b) for (int c = 0; c < N; ++c) {
        dp[0][a][b][c] = dp[1][a][b][c] = -1;
    }
    dp[0][0][0][0] = 1;

    int n; cin >> n;
    int cs; cin >> cs;
    int cf; cin >> cf;
    if (cs > cf) swap(cs, cf);
    
    int ans = 0;
    ans += solve(0, cs-1, cf-cs-1, n-cf);
    ans += solve(1, n-cf, cf-cs-1, cs-1);
    ans %= mod;
    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...