Submission #536367

#	Time	Username	Problem	Language	Result	Execution time	Memory
536367		Old_Pawn	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	35 ms	31780 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
long long memo[2001][2001];

long long dp(int i, int j, const int& n, const int& st, const int& ending) {
    if (i == n) {
        cout << j << endl;
        if (j == 1) return 1;
        return 0;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    long long res = 0;
    long long r1 = 0;
    long long r2 = 0;
    if (i == st || i == ending) {
        if (j >= 1)
            r1 = dp(i + 1, j, n , st, ending);
        r2 = dp(i + 1, j + 1, n ,st, ending);
    } else {
        if (j >= 2)
            r1 = ((j - 1) * dp(i + 1, j - 1, n, st, ending))%mod;
        int ed = (i>st) + (i>ending);
        int tot  = (j - ed <= 0)?1: j - ed;
        r2 = (tot * dp(i + 1,j + 1, n, st, ending))%mod;
    }
    res = (r1 + r2)%mod;
    memo[i][j] = res;

    return res;
}

int main() {
    int n, st, ending;
    while(cin >> n >> st >> ending) {
        memset(memo, 0, sizeof(memo));
        memo[1][1] = 1;
        for(int i=2;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if (i == st || i == ending) {
                    memo[i][j] = (memo[i-1][j] + memo[i-1][j-1])%mod;
                } else {
                    memo[i][j] = (j * memo[i-1][j+1])%mod;
                    int ed = (i>st) + (i>ending);
                    int tot = j - ed;
                    memo[i][j] = (memo[i][j] + (tot * memo[i-1][j-1])%mod)%mod;
                }
            }
        }
        cout << memo[n][1] << endl;
    }
}

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