Submission #1200855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200855		AbdullahIshfaq	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	71 ms	94280 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
void solve(){
	ll n, s, e;
	cin >> n >> s >> e;
	ll dp[n + 1][n + 1][3] = {};
	dp[1][1][(s == 1) | (e == 1)] = 1;
	for(int i = 1; i < n; i ++){
		for(int j = 1; j <= i; j ++){
			if(i + 1 == s or i + 1 == e){
				for(int k = 1; k < 3; k ++){
					dp[i + 1][j][k] += dp[i][j][k - 1];
					dp[i + 1][j][k] %= MOD;
					dp[i + 1][j + 1][k] += dp[i][j][k - 1];
					dp[i + 1][j + 1][k] %= MOD;
				}
			}
			else{
				for(int k = 0; k < 3; k++){
					dp[i + 1][j + 1][k] += dp[i][j][k] * (j + 1 - k);
					dp[i + 1][j + 1][k] %= MOD;
					dp[i + 1][j - 1][k] += dp[i][j][k] * (j - 1);
					dp[i + 1][j - 1][k] %= MOD;
				}
			}
		}
	}
	cout << dp[n][1][2] << '\n';
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll tests = 1;
	// cin >> tests;
	for(ll i = 1; i <= tests; i ++)
		solve();
}

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