Submission #1037359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037359		andrewp	Kangaroo (CEOI16_kangaroo)	C++14	6 / 100	1 ms	2652 KiB

kangaroo

//Dedicated to my love, ivaziva
//https://codeforces.com/blog/entry/92602
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

const int N = 2000 + 20;
const int md = 1e9 + 7;
int n, cs, cf;
int dp[N][N];

int ckadd(int a, int b) {
	a += b;
	if (a >= md) a -= md;
	return a;
}

int ckmul(int a, int b) {
	a *= b;
	if (a >= md) a -= md;
	return a;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	cin >> n >> cs >> cf;

	dp[1][1] = 1;
	for (int e = 2; e <= n; e++) {
		for (int pos = 1; pos <= n; pos++) {
			if (e == cs || e == cf) {
				dp[e][pos] = ckadd(dp[e - 1][pos - 1], dp[e - 1][pos]);
			} else {
				int diff = (e > cs) + (e > cf);
				dp[e][pos] = ckadd(ckmul(dp[e - 1][pos + 1], pos), ckmul(dp[e - 1][pos - 1], pos - diff));
			}
		}
	}
	cout << dp[n][1] << '\n';
}

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