Submission #1327192

#TimeUsernameProblemLanguageResultExecution timeMemory
1327192martin7272772Kangaroo (CEOI16_kangaroo)C++20
100 / 100
13 ms23036 KiB
#include <iostream>
#include <vector>

using namespace std;

long long dp[2005][2005];
const int MOD = 1000000007;

int main() {
    int N, cs, cf;
    if (!(cin >> N >> cs >> cf)) return 0;

    dp[0][0] = 1;

    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (i == cs || i == cf) {
                // If the current number is the start or end point:
                // 1. It can start a new component (at either end of the sequence)
                // 2. It can be added to an existing component
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            } else {
                // If it's a regular number:
                // 1. Create a new component: dp[i-1][j-1] * (number of available slots)
                //    Available slots = j - (is i > cs) - (is i > cf)
                long long choices_new = j;
                if (i > cs) choices_new--;
                if (i > cf) choices_new--;
                
                // 2. Merge two existing components: dp[i-1][j+1] * j
                long long choices_merge = j;

                dp[i][j] = (dp[i - 1][j - 1] * choices_new + dp[i - 1][j + 1] * choices_merge) % MOD;
            }
        }
    }

    // The answer is the state where all N numbers are used and they form 1 single connected path.
    cout << dp[N][1] << endl;

    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...