Submission #832459

#	Time	Username	Problem	Language	Result	Execution time	Memory
832459		Ahmed_Salah7	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	7 ms	16140 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2000 + 10, M = 1e6 + 6, mod = 1e9 + 7;

int n;
int dp[N][N];

int add(int a, int b) {
    return (a + b) % mod;
}

int mul(int a, int b) {
    return (1LL * a * b) % mod;
}

int s, e;

int sol(int i, int j) {
    if (i == n)
        return (j == 1);
    int &ret = dp[i][j];
    if (~ret)
        return ret;
    if (i + 1 == s) {
        ret = sol(i + 1, j); // add to the first comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    if (i + 1 == e) {
        ret = sol(i + 1, j); // add to the last comp
        ret = add(ret, sol(i + 1, j + 1)); // create new comp
        return ret;
    }
    // add newComp
    ret = mul(sol(i + 1, j + 1), (j + 1 - (i + 1 > s) + (i + 1 > e)));
    // merge twoComps
    if (j)
        ret = add(ret, mul(sol(i + 1, j - 1) , (j - 1)));
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, -1, sizeof dp);
    cin >> n >> s >> e;
    cout << sol(0, 0);
}

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