Submission #165796

#	Time	Username	Problem	Language	Result	Execution time	Memory
165796		luciocf	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	80 ms	16324 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e3+10;
const int mod = 1e9+7;

int n;
int cs, cf;

int dp[maxn][maxn];

int solve(int pos, int cc)
{
	if (pos == n+1 && cc != 1) return 0;
	if (pos == n+1) return 1;
	if (dp[pos][cc] != -1) return dp[pos][cc];

	int ans = 0;

	if (pos == cs || pos == cf)
	{
		ans = (ans + solve(pos+1, cc))%mod;
		ans = (ans + solve(pos+1, cc+1))%mod;
		return dp[pos][cc] = ans;
	}

	if (cc >= 2)
	{
		ans = (1ll*ans + 1ll*(cc-1)*solve(pos+1, cc+1))%mod;
		ans = (1ll*ans + 1ll*(cc-1)*solve(pos+1, cc-1))%mod;
	}

	if (pos < cs)
		ans = (1ll*ans + 1ll*solve(pos+1, cc+1))%mod;

	if (pos < cf)
		ans = (1ll*ans + 1ll*solve(pos+1, cc+1))%mod;

	return dp[pos][cc] = ans;
}

int main(void)
{
	scanf("%d %d %d", &n, &cs, &cf);

	if (cs > cf) swap(cs, cf);

	memset(dp, -1, sizeof dp);

	printf("%d\n", solve(2, 1));
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &cs, &cf);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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