Submission #1037287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037287		andrewp	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	5 ms	32348 KiB

kangaroo

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

const int N = 2000 + 20;
const int md = 1e9 + 7;
int n, cs, cf;
int dp[N][N][2];

void ckadd(int &a, int b) {
	a += b;
	if (a >= md) a -= md;
}

void Setup() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < 2; k++) {
				dp[i][j][k] = 0;
			}
		}
	}
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	Setup();

	cin >> n >> cs >> cf;

	int ans = 0;
	dp[cs][1][0] = 1, dp[cs][1][1] = 1;

	for (int id = 2; id <= n; id++) {
		for (int e = 1; e <= n; e++) {
			if (e == cs) {
				continue;
			}
			if (e == cf && id != n) {
				continue;
			}
			for (int ps = 1; ps < e; ps++) {
				ckadd(dp[e][id][1], dp[ps][id - 1][0]);
			}
			for (int ss = e + 1; ss <= n; ss++) {
				ckadd(dp[e][id][0], dp[ss][id - 1][1]);
			}
		}
	}

	for (int i = 0; i < 2; i++) ckadd(ans, dp[cf][n][i]);
	cout << ans << '\n';
}

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