oj.uz

Submission #376647

# Submission time Handle Problem Language Result Execution time Memory
376647 2021-03-11T23:14:07 Z thiago4532 Kangaroo (CEOI16_kangaroo) C++17
0 / 100
 16 ms 31980 KB 
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxn = 2010;
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int n;
int ini, fim;

int solve(int i, int k) {
    if (i > n && k == 1) return 1;
    else if (i > n) return 0;
    if (dp[i][k] != -1) return dp[i][k];

    int caso1 = solve(i+1, k+1);
    int caso2 = (k > 1 ? (i == ini || i == fim ? solve(i+1, k) : solve(i+1, k-1)) : 0);

    if (i == ini || i == fim) return dp[i][k] = (caso1 + caso2)%mod;
    else if (i < ini && i < fim) return dp[i][k] = ( caso1*(k+1) + caso2*(k-1) )%mod;
    else if (i < ini || i < fim) return dp[i][k] = ( caso1*k + caso2*(k-1) )%mod;
    return dp[i][k] = ((k-1)*( caso1 + caso2 ))%mod;
}

int32_t main() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    cin >> ini >> fim;
    cout << solve(1, 0) << '\n';
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 31980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 31980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 31980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 31980 KB Output isn't correct
2 Halted 0 ms 0 KB -