Submission #852240

#	Time	Username	Problem	Language	Result	Execution time	Memory
852240		parsadox2	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	35 ms	16192 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5 , mod = 1e9 + 7;
int n , s , t , dp[N][N] , ans;

int modit(int a)
{
	if(a >= mod)
		return a - mod;
	return a;
}

void solve(int st , int fn)
{
	memset(dp , 0 , sizeof dp);
	dp[0][0] = 1;
	int slm = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		if(i == s)
		{
			for(int j = 1 ; j <= n ; j++)
				dp[i][j] = dp[i - 1][j - st];
			slm++;
			continue;
		}
		if(i == t)
		{
			for(int j = 1 ; j <= n ; j++)
				dp[i][j] = dp[i - 1][j - fn];
			slm++;
			continue;
		}
		for(int j = 1 ; j <= n ; j++)
		{
			dp[i][j] = 1LL * dp[i - 1][j - 1] * max(0 , j - slm) % mod;
			dp[i][j] = modit(dp[i][j] + 1LL * dp[i - 1][j + 1] * j % mod);
		}
	}
	ans = modit(ans + dp[n][1]);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> s >> t;
	int ty = (n & 1 ? 0 : 1);
	solve(1 , 1 ^ ty);
	solve(0 , 0 ^ ty);
	cout << ans << '\n';
	return 0;
}

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