Submission #545534

#	Time	Username	Problem	Language	Result	Execution time	Memory
545534		sidon	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	19 ms	312 KiB

kangaroo

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

const int Z = 2e3+2;
const i64 MOD = 1e9+7;

inline int mul(const i64 &x, const i64 &y) {
	return (x * y) % MOD;
}

inline int add(int x, const int &y) {
	if((x += y) >= MOD) x -= MOD;
	return x;
}

int N, cs, cf, dp[Z] {1}, prv[Z];

int main() {
	cin >> N >> cs >> cf;

	for(int i = 1; i <= N; ++i) {
		copy(dp, dp + Z, prv);
		dp[0] = 0;
		if(i == cs || i == cf) {
			for(int j = 1; j <= N; ++j)
				dp[j] = add(prv[j-1], prv[j]);
		} else {
			for(int j = 1; j <= N; ++j)
				dp[j] = add(mul(prv[j+1], j), mul(prv[j-1], j - (i > cs) - (i > cf)));
		}
	}

	cout << dp[1];
}

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