Submission #481052

#	Time	Username	Problem	Language	Result	Execution time	Memory
481052		naman1601	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	15 ms	22988 KiB

kangaroo

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"

#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;


const int maxn = 2005;
big dp[maxn][maxn] = {0};
int n, s, f;


void solve() {

	// fr(i, 0, maxn) fr(j, 0, maxn) dp[i][j] = -1;
	cin >> n >> s >> f;

	dp[1][1] = 1;

	fr(i, 2, n + 1) {

		fr(j, 1, i + 1) {

			if(i == s || i == f) {

				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				dp[i][j] %= mod;
				continue;
			}

			dp[i][j] = dp[i - 1][j + 1] * j + dp[i - 1][j - 1] * (j - (i > s) - (i > f));
			dp[i][j] %= mod;
		}
	}

	cout << dp[n][1] << nl;
}


int main() {
	
	speed;

	int TC = 1;
	// cin >> TC;

	#ifdef naman1601
	freopen("kangaroo.in", "r", stdin);
	freopen("kangaroo.out", "w", stdout);
	#endif

	for(int tc = 1; tc <= TC; tc++) {

		// cout << "Case #" << tc << ": ";
		solve();
	}

	return 0;
}

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