Submission #5281525

Source Code Expand

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;
std::vector<std::vector<std::vector<LL>>>memo;

LL dp(LL i, LL a, LL b)
{
	if (a < 0 || b < 0) return 0;
	if (i == -1) return (a == 0 && b == 0 ? 1 : 0);
	if (memo[i][a][b] != -1) return memo[i][a][b];
	LL res1 = (dp(i - 1, a, b - 1) * a) % mod;
	LL res2 = (dp(i - 1, a - 1, b) * b) % mod;
	LL res3 = (dp(i - 1, a - 1, b - 1) * (i - (a - 1) - (b - 1))) % mod;
	LL res4 = dp(i - 1, a, b);
	return memo[i][a][b] = (res1 + res2 + res3 + res4) % mod;
}

int main()
{
	LL N, A, B;
	in >> N >> A >> B;

	memo.resize(N, std::vector<std::vector<LL>>(A + 1, std::vector<LL>(B + 1, -1)));
	out << dp(N - 1, A, B) << std::endl;
}

Submission Info

Submission Time
Task F - Flexible Permutation
User Bwambocos
Language C++14 (GCC 5.4.1)
Score 600
Code Size 806 Byte
Status AC
Exec Time 265 ms
Memory 55168 KiB

Judge Result

Set Name all small sample
Score / Max Score 300 / 300 300 / 300 0 / 0
Status
AC × 44
AC × 20
AC × 4
Set Name Test Cases
all 21_zerozero, 22_zerozero, 23_a_zero, 24_a_zero, 25_zero_b, 26_zero_b, 27_cyclic, 28_cyclic, 29_cyclic, 30_cyclic, 31_large_random, 32_large_random, 33_large_random, 34_large_random, 35_large_random, 36_large_large, 37_large_large, 38_large_large, 39_large_large, 40_large_large, sample01, sample02, sample03, sample04, small_01_random, small_02_random, small_03_random, small_04_random, small_05_random, small_06_random, small_07_random, small_08_random, small_09_random, small_10_random, small_11_random, small_12_random, small_13_random, small_14_random, small_15_random, small_16_random, small_17_random, small_18_random, small_19_random, small_20_random
small small_01_random, small_02_random, small_03_random, small_04_random, small_05_random, small_06_random, small_07_random, small_08_random, small_09_random, small_10_random, small_11_random, small_12_random, small_13_random, small_14_random, small_15_random, small_16_random, small_17_random, small_18_random, small_19_random, small_20_random
sample sample01, sample02, sample03, sample04
Case Name Status Exec Time Memory
21_zerozero AC 1 ms 256 KiB
22_zerozero AC 1 ms 256 KiB
23_a_zero AC 8 ms 5120 KiB
24_a_zero AC 8 ms 4864 KiB
25_zero_b AC 2 ms 896 KiB
26_zero_b AC 2 ms 896 KiB
27_cyclic AC 9 ms 5120 KiB
28_cyclic AC 8 ms 4224 KiB
29_cyclic AC 4 ms 1536 KiB
30_cyclic AC 4 ms 1536 KiB
31_large_random AC 8 ms 3456 KiB
32_large_random AC 97 ms 21504 KiB
33_large_random AC 90 ms 24320 KiB
34_large_random AC 8 ms 3072 KiB
35_large_random AC 22 ms 8320 KiB
36_large_large AC 265 ms 54912 KiB
37_large_large AC 253 ms 55168 KiB
38_large_large AC 226 ms 54272 KiB
39_large_large AC 225 ms 53888 KiB
40_large_large AC 225 ms 54400 KiB
sample01 AC 1 ms 256 KiB
sample02 AC 1 ms 256 KiB
sample03 AC 1 ms 256 KiB
sample04 AC 66 ms 18176 KiB
small_01_random AC 1 ms 256 KiB
small_02_random AC 1 ms 256 KiB
small_03_random AC 1 ms 256 KiB
small_04_random AC 1 ms 256 KiB
small_05_random AC 1 ms 256 KiB
small_06_random AC 1 ms 256 KiB
small_07_random AC 1 ms 256 KiB
small_08_random AC 1 ms 256 KiB
small_09_random AC 1 ms 256 KiB
small_10_random AC 1 ms 256 KiB
small_11_random AC 1 ms 256 KiB
small_12_random AC 1 ms 256 KiB
small_13_random AC 1 ms 256 KiB
small_14_random AC 1 ms 256 KiB
small_15_random AC 1 ms 256 KiB
small_16_random AC 1 ms 256 KiB
small_17_random AC 1 ms 256 KiB
small_18_random AC 1 ms 256 KiB
small_19_random AC 1 ms 256 KiB
small_20_random AC 1 ms 256 KiB