제출 #536361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536361		Old_Pawn	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	13 ms	31576 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) {
        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 + mod) * 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) {
        st--;
        ending--;
        memset(memo, -1, sizeof(memo));
        cout << dp(0 ,0, n, st, ending) << endl;
    }
}

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