Submission #472000

#	Time	Username	Problem	Language	Result	Execution time	Memory
472000		DEQK	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	27 ms	14252 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

const int N = 2020;
const int mod = 1e9 + 7;
int n, a, b;
int dp[N][N];
void inc(int &x,int y) {
	x += y;
	if(x >= mod) x -= mod;
}
int main() {
	scanf("%d%d%d", &n, &a, &b);
	dp[1][1] = 1;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= i; j++) {
			if(dp[i][j] == 0) continue; // doesnt contribute to answer
			if(i + 1 == a || i + 1 == b) {
				inc(dp[i + 1][j], dp[i][j]);
				inc(dp[i + 1][j + 1], dp[i][j]);
			} else {
				inc(dp[i + 1][j - 1], dp[i][j] * 1ll * (j - 1) % mod);
				inc(dp[i + 1][j + 1], dp[i][j] * 1ll * (j + 1 - (i + 1 > a) - (i + 1 > b)) % mod); // can not be to the left a and to the right b
			}
		}
	}
	printf("%d", dp[n][1]);
}

Compilation message (stderr)

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

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