Submission #1113185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113185		Jawad_Akbar_JJ	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	2048 ms	121928 KiB

kangaroo

#include <iostream>

using namespace std;
int dp[200][200][200][2][2], seen[200][200][200][2][2], mod = 1e9 + 7;

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

int calc(int a, int b, int c, bool pos, bool rgt){
	if (seen[a][b][c][pos][rgt])
		return dp[a][b][c][pos][rgt];
	seen[a][b][c][pos][rgt] = 1;

	if (pos){
		for (int i=1;i<=b;i++)
			Add(dp[a][b][c][pos][rgt], calc(a, b - i, c + i - 1, 1, !rgt) * (rgt == 1));
		for (int i=1;i<=a;i++)
			Add(dp[a][b][c][pos][rgt], calc(a - i, i - 1, b + c, 0, !rgt) * (rgt == 1));
		for (int i=1;i<=c;i++)
			Add(dp[a][b][c][pos][rgt], calc(a, b + i - 1, c - i, 1, !rgt) * (rgt == 0));
		return dp[a][b][c][pos][rgt];
	}
	for (int i=1;i<=a;i++)
		Add(dp[a][b][c][pos][rgt], calc(a - i, b + i - 1, c, 0, !rgt) * (rgt == 1));
	for (int i=1;i<=b;i++)
		Add(dp[a][b][c][pos][rgt], calc(a + i - 1, b - i, c, 0, !rgt) * (rgt == 0));
	for (int i=1;i<=c;i++)
		Add(dp[a][b][c][pos][rgt], calc(a + b, i - 1, c - i, 1, !rgt) * (rgt == 0));
	return dp[a][b][c][pos][rgt];
}

int main(){
	int n, st, en, Ans = 0;
	cin>>n>>st>>en;

	if (st > en)
		swap(st, en);
	seen[0][0][0][0][0] = seen[0][0][0][1][1] = 1;
	dp[0][0][0][0][0]   = dp[0][0][0][1][1]   = 1;

	for (bool b : {0, 1})
		Add(Ans, calc(st - 1, en - st - 1, n - en, 0, b));
	cout<<Ans<<'\n';
}

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