Submission #741054

#	Time	Username	Problem	Language	Result	Execution time	Memory
741054		scurcic	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	45 ms	31800 KiB

kangaroo

#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int oo = 2e3+7;

int n, s, e;
ll dp[oo][oo];
ll gdp(int i, int j) {
    if (dp[i][j] != -1) return dp[i][j];
    dp[i][j] = 0;
    bool ee = i == s || i == e;
    if (j > 1)
    dp[i][j] += (ee ? 1 : (j - (i>=s) - (i>=e))) * gdp(i-1,j-1);
    dp[i][j] %= mod;
    dp[i][j] += (ee ? 1 : j) * gdp(i-1,(ee ? j : j+1));
    dp[i][j] %= mod;
    return dp[i][j];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> e;
    for (int i = 1; i <= n; i++) for (int j = 0; j <= n; j++) dp[i][j] = -1;
    dp[1][1] = 1;
    cout << gdp(n, 1) << endl;
}

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