Submission #1126660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126660		omar123	Kangaroo (CEOI16_kangaroo)	C++20	0 / 100	0 ms	324 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> dp;
int n, s, e;
const int mod = 1000000007;
int solve(const int i, const int j){
    if(i == 1) {
        if (j == 1) return 1;
        return 0;
    }
    if(i < 0 || i > n) return 0;
    if(j < 0 || j > n) return 0;

    int &ans = dp[i][j];
    if(ans != -1) return ans;

    if(i == s || i == e) {
        int p1 = solve(i - 1, j - 1);
        int p2 = solve(i - 1, j);
        return ans = (p1 + p2) % mod;
    }

    if(i > e) {
        int p1 = solve(i - 1, j - 1) * (j - 2LL) % mod;
        int p2 = solve(i - 1, j) * ((j - 2) * 2LL + 2) % mod; 
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod;
        return ans = (p1 + p2 + p3) % mod;
    }

    if(i > s) {
        int p1 = solve(i - 1, j - 1) * 1LL * (j - 1) % mod; // new component
        int p2 = solve(i - 1, j) * 1LL * ((j - 1) * 2 + 1) % mod; // same component
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod; // merge two components
        return ans = (p1 + p2 + p3) % mod;
    }

    if(i < s) {
        int p1 = solve(i - 1, j - 1) * 1LL * j % mod; // new component
        int p2 = solve(i - 1, j) * 1LL * (2 * j) % mod; // same component
        int p3 = solve(i - 1, j + 1) * 1LL * j % mod; // merge two components
        return ans = (p1 + p2 + p3) % mod;
    }

    assert(false);
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("kangaroo.in", "r", stdin);
    // freopen("kangaroo.out", "w", stdout);

    
    while(cin >> n >> s >> e) {
        dp = vector<vector<int>> (n + 1, vector<int>(n + 1, -1));
        if(s > e) swap(s, e);
        cout << solve(n, n) << '\n';
    }
  
   
        
    return 0;
}

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