Submission #1004068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004068		ef10	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	50 ms	31836 KiB

kangaroo

// Source: https://usaco.guide/general/io

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

#define LL long long
#define MODULE 1000000007

int main() {
	std::ifstream input;
    input.open("kangaroo.in");
    std::ofstream output;
    output.open("kangaroo.out");
	LL N, s, f;
	cin >> N >> s >> f;
	LL ep = 0;
	LL dp[N+5][N+5]; memset(dp,0,sizeof(dp));
	dp[1][1] = 1;
	if (s==1 || f==1) {
		ep++;
	}
	for (LL i = 2; i <= N; i++) {
		for (LL j = 1; j <= N; j++) {
			if (i == s || i == f) {
				if (j == 1) ep++;
				dp[i][j] += dp[i-1][j-1];
				dp[i][j] %= MODULE;
				dp[i][j] += dp[i-1][j];
				dp[i][j] %= MODULE;
				continue;
			}
			if (j-ep > 0) {
				dp[i][j] += (dp[i-1][j-1] * (j-ep)) % MODULE;
				dp[i][j] %= MODULE;
			}
			dp[i][j] += (dp[i-1][j+1]*j) % MODULE;
			dp[i][j] %= MODULE;
		}
	}
	cout << dp[N][1] << endl;
}

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