Submission #613907

#	Time	Username	Problem	Language	Result	Execution time	Memory
613907		lorenzoferrari	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	23 ms	62884 KiB

kangaroo

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

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