oj.uz

Submission #405986

# Submission time Handle Problem Language Result Execution time Memory
405986 2021-05-17T06:06:09 Z AriaH Kangaroo (CEOI16_kangaroo) C++11
51 / 100
 103 ms 75328 KB 
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 2e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

ll F[N], I[N];

ll E(ll r, ll n)
{
	if(r > n || r < 0) return 0;
	return F[n] * I[r] % mod * I[n - r] % mod;
}

int n, s, f;

ll dp[N][4][N][N]; /// tedad halati ke toye i taye aval T ta masire ye samt baste vojod dare / a / b

int main()
{
	F[0] = 1;
	for(int i = 1; i < N; i ++) F[i] = F[i - 1] * i % mod;
	I[N - 1] = pw(F[N - 1], mod - 2, mod);
	for(int i = N - 2; ~i; i --)
	{
		I[i] = I[i + 1] * (i + 1) % mod;
	}
	scanf("%d%d%d", &n, &s, &f);
	dp[0][0][0][0] = 1;
	for(int i = 0; i < n; i ++)
	{
		for(int c = 0; c < 3; c ++)
		{
			for(int a = 0; a <= i; a ++)
			{
				for(int b = 0; b <= i - a; b ++)
				{
					ll cu = dp[i][c][a][b];
					if(!cu) continue;
					if(i + 1 == f || i + 1 == s)
					{
						/// match be ye a
						if(a) dp[i + 1][c + 1][a - 1][b] = (dp[i + 1][c + 1][a - 1][b] + cu * a) % mod;
						/// match be ye b
						if(b > 1) dp[i + 1][c + 1][a][b - 2] = (dp[i + 1][c + 1][a][b - 2] + cu * b) % mod;
						/// match be ye c
						if(c) dp[i + 1][c - 1][a][b] = (dp[i + 1][c - 1][a][b] + cu) % mod;
						dp[i + 1][c + 1][a][b] = (dp[i + 1][c + 1][a][b] + cu) % mod;
					}
					else
					{
						/// match be 2 ta a
						if(a > 1) dp[i + 1][c][a - 2][b + 2] = (dp[i + 1][c][a - 2][b + 2] + cu * E(2, a)) % mod;
						/// match be 2 ta b
						if(b > 1)
						{
							dp[i + 1][c][a][b - 2] = (dp[i + 1][c][a][b - 2] + cu * b * (b - 2) / 2) % mod;
						}
						/// match be ye a ye b
						if(a && b)
						{
							dp[i + 1][c][a - 1][b] = (dp[i + 1][c][a - 1][b] + cu * a * b) % mod;
						}
						/// match be 2 ta c
						if(c > 1)
						{
							dp[i + 1][c - 2][a][b] = (dp[i + 1][c - 2][a][b] + cu) % mod;
						}
						///match be ye c va ye a
						if(c && a)
						{
							dp[i + 1][c][a - 1][b] = (dp[i + 1][c][a - 1][b] + cu * a * c) % mod;
						}
						/// match be ye c va ye b
						if(c > 0 && b > 1)
						{
							dp[i + 1][c][a][b - 2] = (dp[i + 1][c][a][b - 2] + cu * c * b) % mod;
						}
						dp[i + 1][c][a + 1][b] = (dp[i + 1][c][a + 1][b] + cu) % mod;
					}
				}
			}
		}
	}
	/*for(int i = 0; i <= n; i ++)
	{
		for(int c = 0; c < 3; c ++)
		{
			for(int a = 0; a <= i; a ++)
			{
				for(int b = 0; b <= i - a; b ++)
				{
					if(!dp[i][c][a][b]) continue;
					printf("i = %d c = %d a = %d b = %d dp = %lld\n", i, c, a, b, dp[i][c][a][b]);
				}
			}
		}
	}
	*/
	printf("%lld", dp[n][0][0][0]);
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d", &n, &s, &f);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 3 ms 2608 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 2 ms 2228 KB Output is correct
11 Correct 3 ms 1996 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 3 ms 2608 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 2 ms 2228 KB Output is correct
11 Correct 3 ms 1996 KB Output is correct
12 Correct 66 ms 58352 KB Output is correct
13 Correct 60 ms 57464 KB Output is correct
14 Correct 39 ms 34684 KB Output is correct
15 Correct 60 ms 51156 KB Output is correct
16 Correct 64 ms 56468 KB Output is correct
17 Correct 60 ms 52800 KB Output is correct
18 Correct 37 ms 31788 KB Output is correct
19 Correct 66 ms 60100 KB Output is correct
20 Correct 68 ms 61996 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 3 ms 2608 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 2 ms 2228 KB Output is correct
11 Correct 3 ms 1996 KB Output is correct
12 Correct 66 ms 58352 KB Output is correct
13 Correct 60 ms 57464 KB Output is correct
14 Correct 39 ms 34684 KB Output is correct
15 Correct 60 ms 51156 KB Output is correct
16 Correct 64 ms 56468 KB Output is correct
17 Correct 60 ms 52800 KB Output is correct
18 Correct 37 ms 31788 KB Output is correct
19 Correct 66 ms 60100 KB Output is correct
20 Correct 68 ms 61996 KB Output is correct
21 Runtime error 103 ms 75328 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -