oj.uz

Submission #24606

# Submission time Handle Problem Language Result Execution time Memory
24606 2017-06-10T17:54:05 Z bill_kondo Kangaroo (CEOI16_kangaroo) C++14
6 / 100
 0 ms 2052 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 2e3 + 10;
const ll mod = 1e9 + 7;

int n, cs, cf;

ll dp[2][1 << 8][8];

ll f (int dir, int mask, int cur)
{
	if (dp[dir][mask][cur] == -1)
	{
		if (!mask)
		{
			if (cur != cf)
				return dp[dir][mask][cur] = 0;

			return dp[dir][mask][cur] = 1;
		}

		dp[dir][mask][cur] = 0;

		if (dir)
		{
			for (int i = cur; i < n; ++i)
				if ((1 << i) & mask)
					dp[dir][mask][cur] = (dp[dir][mask][cur] + f (dir ^ 1, mask - (1 << i), i)) % mod;
		}
		else
		{
			for (int i = cur; i >= 0; --i)
				if ((1 << i) & mask)
					dp[dir][mask][cur] = (dp[dir][mask][cur] + f (dir ^ 1, mask - (1 << i), i)) % mod;
		}
	}

	return dp[dir][mask][cur];
}

void solve_small ()
{
	memset (dp, -1, sizeof (dp));

	int total = (1 << n) - 1;
	cout << (f (0, total - (1 << cs), cs) + f (1, total - (1 << cs), cs)) % mod << '\n';
}

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

	--cs;
	--cf;

	if (n <= 8)
	{
		solve_small();
		return 0;
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2052 KB Output is correct
2 Correct 0 ms 2052 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2052 KB Output is correct
2 Correct 0 ms 2052 KB Output is correct
3 Incorrect 0 ms 2052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2052 KB Output is correct
2 Correct 0 ms 2052 KB Output is correct
3 Incorrect 0 ms 2052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2052 KB Output is correct
2 Correct 0 ms 2052 KB Output is correct
3 Incorrect 0 ms 2052 KB Output isn't correct
4 Halted 0 ms 0 KB -