oj.uz

Submission #963011

# Submission time Handle Problem Language Result Execution time Memory
963011 2024-04-14T11:01:00 Z Ghetto Kangaroo (CEOI16_kangaroo) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 2e3 + 5;
const lint MOD = 1e9 + 7;

int n;
int s, f;

lint mod(lint x) {
    return x % MOD;
}

lint dp[MAX_N][MAX_N];
void do_dp() {
    dp[1][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int c = 1; c <= n; c++) {
            // cout << i << ", " << c << ": " << dp[i][c] << endl;

            if ((i + 1) == s || (i + 1) == f) {
                dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + dp[i][c]);
                dp[i + 1][c] = mod(dp[i + 1][c] + dp[i][c]);
                continue;
            }

            lint mult = c + 1;
            mult -= (bool) (i > s);
            mult -= (bool) (i > f);
            
            dp[i + 1][c + 1] = mod(dp[i + 1][c + 1] + mod(dp[i][c] * mult));
            dp[i + 1][c - 1] = mod(dp[i + 1][c - 1] + mod(dp[i][c] * (c - 1)));
        }
    }
}

int main() {
    // freopen("kangaroo.in", "r", stdin);

    cin >> n >> s >> f;
    if (s > f) swap(s, f);

    do_dp();
    cout << dp[n][1] << '\n';
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -