oj.uz

Submission #526608

# Submission time Handle Problem Language Result Execution time Memory
526608 2022-02-15T14:58:51 Z Arnch Ruins 3 (JOI20_ruins3) C++17
58 / 100
 3 ms 848 KB 
// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

const ll inf = 1e18, N = 650, mod = 1e9 + 7, pr = 1000696969;

int a[N];
ll dp[N], sf[N][N];
ll fac[N], rfac[N];
bool mark[N];

ll poww(ll x, ll y) {
	ll res = 1;
	for(; y; y /= 2, x = x * x % mod)
		if(y & 1) {
			res = res * x % mod;
		}
	return res;
}

void pre() {
	fac[0] = 1;
	for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
	for(int i = 0; i < N; i++) rfac[i] = poww(fac[i], mod - 2);
}

ll choose(ll x, ll y) {
	if(x > y) return 0;
	if(x == y) return 1;
	ll ans = fac[y];
	ans *= rfac[x];
	ans %= mod;
	ans *= rfac[y - x];
	ans %= mod;
	return ans;
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	pre();
	
	int n; cin >>n;
	for(int i = 1; i <= n; i++) cin >>a[i], mark[a[i]] = 1;
	
	dp[0] = 1;
	for(int len = 1; len <= n; len++) {
		for(int j = 0; j < len; j++) {
			ll val = dp[j] * dp[len - j - 1];
			val %= mod;
			val *= choose(j, len - 1);
			val %= mod;
			val *= j + 2; val %= mod;
			dp[len] += val;
			dp[len] %= mod;
		}
	}

	int c0 = 0, c1 = 0;
	
	
	sf[2 * n + 1][0] = 1;
	for(int i = 2 * n; i > 0; i--) {
		if(mark[i] == 0) {
			for(int R = 0; R <= c1; R++) {
				sf[i][R] = sf[i + 1][R] * (max(0, R - c0));	
				sf[i][R] %= mod;
			}
			c0++;
			continue;
		}
		for(int R = 0; R <= c1 + 1; R++) {
			int k = c1 - R + 1;
			sf[i][R] = sf[i + 1][R];
			sf[i][R] %= mod;
			for(int j = 0; j < R; j++) {
				ll val = dp[j] * sf[i + 1][R - j - 1];
				val %= mod;
				val *= choose(j, c1 - (R - j) + 1);
				val %= mod;
				val *= j + 2;
				val %= mod;
				sf[i][R] += val;
				sf[i][R] %= mod;
			}
		}
		c1++;
	}
	
	ll ans = sf[1][n];
	ans *= poww(poww(2, n), mod - 2);
	ans %= mod;

	cout<<ans;

	
    return 0;
}

Compilation message

ruins3.cpp: In function 'int main()':
ruins3.cpp:88:8: warning: unused variable 'k' [-Wunused-variable]
   88 |    int k = c1 - R + 1;
      |        ^

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
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
52.0 / 52.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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 1 ms 844 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 848 KB Output is correct
16 Correct 1 ms 836 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 844 KB Output is correct
19 Correct 1 ms 844 KB Output is correct
20 Correct 1 ms 844 KB Output is correct

Subtask #3
0 / 42.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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 1 ms 844 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 848 KB Output is correct
16 Correct 1 ms 836 KB Output is correct
17 Correct 1 ms 716 KB Output is correct
18 Correct 1 ms 844 KB Output is correct
19 Correct 1 ms 844 KB Output is correct
20 Correct 1 ms 844 KB Output is correct
21 Runtime error 3 ms 460 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -