Submission #835239

#	Time	Username	Problem	Language	Result	Execution time	Memory
835239		Ahmad_Elsisy	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	54 ms	16212 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;


const int N = 2004, MOD = 1e9 + 7;
int memo[N][N], n;

int add(int a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
    while(a < 0)
        a += MOD;
    return a;
}

int mul(int a, int b) {
    return (1ll * (a % MOD) * (b % MOD)) % MOD;
}
int s, e;

int solve(int i, int j) {
    if(i == n + 1)
        return j == 1;
    int &ret = memo[i][j];
    if(~ret)
        return ret;
    bool putStart = (i > s);
    bool putEnd = (i > e);
    ret = 0;
    // add to comp
    if(i == s) {
        if(!(j == 1 && putEnd && i < n))
            ret = add(ret, solve(i + 1, j));
        ret = add(ret, solve(i + 1, j + 1));
        return ret;
    }
    if(i == e) {
        if(!(j == 1 && putStart && i < n))
            ret = add(ret, solve(i + 1, j));
        ret = add(ret, solve(i + 1, j + 1));
        return ret;
    }

    // new comp ?(x)?(y)?(z)?
    ret = add(ret, mul(max(0, j + 1 - putStart - putEnd), solve(i + 1, j + 1)));
    // merge two adjacent comps
    if(j > 1)
        ret = add(ret, mul(j - 1, solve(i + 1, j - 1)));
    return ret;
}
void solve() {
    cin >> n >> s >> e;
    memset(memo , -1 ,sizeof memo);
    cout << solve(1, 0) << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc = 1;
//    cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

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