Submission #110848

#	Time	Username	Problem	Language	Result	Execution time	Memory
110848		mosesmayer	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	82 ms	31992 KiB

kangaroo

#include <iostream>
#include <iomanip>
#include <cstring>
using namespace std;
typedef long long LL;

const LL mod = 1e9 + 7;
int n, s, t;

LL dp[2005][2005];

LL f(int pos, int cc){
	if (pos > n) return cc == 1; // base case, reached if cc = 1 when we reach end position
	if (pos > 1 && cc < 1) return 0; // once pos after 1, impossible as we have at least 1 contiguous component
	LL &ret = dp[pos][cc];
	if (ret != -1) return ret;
	ret = 0;
	//special case --> endpoints
	if (!(pos ^ s) || !(pos ^ t)){ // UwU ಠ_ಠ
		(ret += f(pos + 1, cc)) %= mod; // already ada.
		(ret += f(pos + 1, cc + 1)) %= mod; // desired endpoint not used
	} else {
		int ends = 2 - (pos > s) - (pos > t);
		//new component --> two adjacent will be smaller
		(ret += f(pos + 1, cc + 1) * (cc - 1 + ends)) %= mod; // create new component, ends == extra empty spaces due to ends
		//merge component --> larger than two adjacent
		(ret += f(pos + 1, cc - 1) * (cc - 1)) %= mod;
	}
	return ret;
}

int main(){
	cin >> n >> s >> t;
	memset(dp, -1, sizeof(dp));
	cout << f(1, 0) << '\n';
	return 0;
}

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