Submission #604706

#	Time	Username	Problem	Language	Result	Execution time	Memory
604706		SeDunion	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	596 KiB

kangaroo

#include<iostream>

using namespace std;

const int mod = 1e9 + 7;

int mult(int x, int y) {
	return x * 1ll * y % mod;
}

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

int ad(int x, int y) {
	add(x, y);
	return x;
}

int dp[22][22][22][2];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, cs, cf;
	cin >> N >> cs >> cf;
	dp[1][1][1][0] = dp[1][1][1][1] = 1;
	for (int n = 1 ; n < N ; ++ n) {
		for (int x = 1 ; x <= n ; ++ x) {
			for (int y = 1 ; y <= n ; ++ y) {
				for (int z = 1 ; z <= y ; ++ z) {
					add(dp[n+1][x+(z<=x)][z][0], dp[n][x][y][1]);
				}
				for (int z = y + 1 ; z <= n + 1 ; ++ z) {
					add(dp[n+1][x+(z<=x)][z][1], dp[n][x][y][0]);
				}
			}
		}
	}
	cout << ad(dp[N][cs][cf][0], dp[N][cs][cf][1]);
}

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