Submission #59105

#	Time	Username	Problem	Language	Result	Execution time	Memory
59105		gabrielsimoes	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	115 ms	32340 KiB

kangaroo

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

typedef long long ll;
const int MAXN = 2000;
const ll MOD = 1000000007;

int n, cs, cf;
ll dp[MAXN][MAXN];

ll f(int i, int k) {
	if (k < 0) return 0;
	if (i == n-1) return k == 0 ? 1 : 0;

	ll &ret = dp[i][k];
	if (ret != -1) return ret;
	ret = 0;
	
	ll ks = i > cs;
	ll kf = i > cf;
	
	if (i == cs || i == cf) {
		ret += f(i+1, k);
		ret += f(i+1, k-1) * k;
	} else {
		ret += f(i+1, k+1);
		ret += f(i+1, k-1) * (k*(k-1) + ks*k + k*kf);
	}
	
	return ret %= MOD;
}

int main() {
	memset(dp, -1, sizeof(dp));
	scanf("%d %d %d", &n, &cs, &cf);
	cs--;
	cf--;
	printf("%d\n", f(0, 0));
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:38:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  printf("%d\n", f(0, 0));
                 ~~~~~~~^
kangaroo.cpp:35: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