oj.uz

답안 #529045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529045 2022-02-22T03:19:36 Z 8e7 Tents (JOI18_tents) C++17
48 / 100
 2000 ms 93180 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 3005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
void madd(int &x, int v) {
	x += v - mod; x += mod & (x>>31);
}
ll comb[maxn][maxn], fac[maxn], cat[maxn][maxn], po[maxn];
ll c(int n, int m) {
	if (m > n || m < 0) return 0;
	return comb[n][m];
}
int main() {
	io
	po[0] = 1;
	for (int i = 1;i < maxn;i++) po[i] = po[i-1] * 4 % mod;
	fac[0] = 1;
	for (int i = 1;i < maxn;i++) fac[i] = fac[i-1] * i % mod;
	comb[0][0] = 1;
	for (int i = 1;i < maxn;i++) {
		for (int j = 0;j <= i;j++) {
			comb[i][j] = (comb[i-1][j] + (j ? comb[i-1][j-1] : 0)) % mod;
		}
	}
	cat[0][0] = 1;
	for (int i = 1;i < maxn-1;i++) {
		for (int j = 0;j <= i;j++) {
			if (j) cat[i][j] = (cat[i][j] + cat[i-1][j-1])%mod;
			cat[i][j] = (cat[i][j] + cat[i-1][j+1] * (j+1)%mod)%mod;
		}
	}

	int n, m;
	cin >> n >> m;
	ll ans = 0;
	for (int i = 0;i < maxn;i++) {
		for (int j = 0;j < maxn;j++) {
			if (2*i + j > n || i + 2 * j > m) continue;
			ll val = c(n, 2*i + j) * c(m, i + 2*j) % mod * 
					c(2*i + j, j)%mod * c(i + 2*j, i)%mod * 
					cat[2*i][0]%mod * cat[2*j][0]%mod * fac[i]%mod * fac[j]%mod;
			ll s = 0;
			int sx = n - (2*i+j), sy = m - (i+2*j);
			for (int k = 0;k <= min(sx, sy);k++) {
				s = (s + c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod)%mod; 	
				//debug(i, j, sx, sy, k, c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod);
			}
			//debug(i, j, val, s);
			debug(i, j, val*s);
			ans = (ans + val * s)%mod;
			//debug(ans);
		}
	}
	cout << (ans+mod-1)%mod << endl;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
tents.cpp:66:4: note: in expansion of macro 'debug'
   66 |    debug(i, j, val*s);
      |    ^~~~~

Subtask #1
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 93084 KB Output is correct
2 Correct 91 ms 93000 KB Output is correct
3 Correct 94 ms 93048 KB Output is correct
4 Correct 88 ms 93092 KB Output is correct
5 Correct 92 ms 93020 KB Output is correct
6 Correct 93 ms 93036 KB Output is correct
7 Correct 90 ms 93040 KB Output is correct
8 Correct 105 ms 93136 KB Output is correct
9 Correct 104 ms 93072 KB Output is correct
10 Correct 99 ms 93092 KB Output is correct
11 Correct 91 ms 93168 KB Output is correct
12 Correct 102 ms 93056 KB Output is correct

Subtask #2
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 93084 KB Output is correct
2 Correct 91 ms 93000 KB Output is correct
3 Correct 94 ms 93048 KB Output is correct
4 Correct 88 ms 93092 KB Output is correct
5 Correct 92 ms 93020 KB Output is correct
6 Correct 93 ms 93036 KB Output is correct
7 Correct 90 ms 93040 KB Output is correct
8 Correct 105 ms 93136 KB Output is correct
9 Correct 104 ms 93072 KB Output is correct
10 Correct 99 ms 93092 KB Output is correct
11 Correct 91 ms 93168 KB Output is correct
12 Correct 102 ms 93056 KB Output is correct
13 Correct 91 ms 93180 KB Output is correct
14 Correct 94 ms 92996 KB Output is correct
15 Execution timed out 2090 ms 93012 KB Time limit exceeded
16 Halted 0 ms 0 KB -