답안 #472798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472798 2021-09-14T10:46:49 Z prvocislo Tents (JOI18_tents) C++17
100 / 100
268 ms 63312 KB
#include <iostream>
typedef long long ll;
using namespace std;

const int mod = 1e9 + 7, maxn = 3005;
int add(const int& a, const int& b) { return (a + b) % mod; }
int mul(const int& a, const int& b) { return (a * 1ll * b) % (ll)mod; }
void upd(int& a, const int& b) { a = (a + b) % mod; }
int dp[maxn][maxn], p[maxn][maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	p[0][0] = 1;
	for (int i = 1; i < maxn; i++)
	{
		p[i][0] = p[i][i] = 1;
		for (int j = 1; j < i; j++) p[i][j] = add(p[i - 1][j - 1], p[i - 1][j]);
	}
	dp[0][0] = 1;
	int h, w;
	cin >> h >> w;
	for (int i = 0; i < h; i++) for (int j = 0; j < w; j++)
	{
		upd(dp[i + 1][j + 1], mul(dp[i][j], mul(4, j + 1)));
		if (i + 2 <= h) upd(dp[i + 2][j + 1], mul(dp[i][j], mul(i + 1, j + 1)));
		if (j + 2 <= w) upd(dp[i + 1][j + 2], mul(dp[i][j], (j + 1) * (j + 2)/ 2));
	}
	int ans = 0;
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++)
	{
		int a = mul(dp[i][j], mul(p[h][i], p[w][j]));
		upd(ans, a);
	}
	cout << ans << "\n";
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 27972 KB Output is correct
2 Correct 24 ms 27960 KB Output is correct
3 Correct 27 ms 28184 KB Output is correct
4 Correct 24 ms 28756 KB Output is correct
5 Correct 26 ms 28236 KB Output is correct
6 Correct 20 ms 28952 KB Output is correct
7 Correct 21 ms 28364 KB Output is correct
8 Correct 21 ms 29008 KB Output is correct
9 Correct 19 ms 28416 KB Output is correct
10 Correct 21 ms 29252 KB Output is correct
11 Correct 20 ms 27936 KB Output is correct
12 Correct 27 ms 29472 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 27972 KB Output is correct
2 Correct 24 ms 27960 KB Output is correct
3 Correct 27 ms 28184 KB Output is correct
4 Correct 24 ms 28756 KB Output is correct
5 Correct 26 ms 28236 KB Output is correct
6 Correct 20 ms 28952 KB Output is correct
7 Correct 21 ms 28364 KB Output is correct
8 Correct 21 ms 29008 KB Output is correct
9 Correct 19 ms 28416 KB Output is correct
10 Correct 21 ms 29252 KB Output is correct
11 Correct 20 ms 27936 KB Output is correct
12 Correct 27 ms 29472 KB Output is correct
13 Correct 20 ms 27980 KB Output is correct
14 Correct 24 ms 37208 KB Output is correct
15 Correct 159 ms 60484 KB Output is correct
16 Correct 28 ms 30404 KB Output is correct
17 Correct 49 ms 35568 KB Output is correct
18 Correct 68 ms 38540 KB Output is correct
19 Correct 195 ms 62192 KB Output is correct
20 Correct 148 ms 56660 KB Output is correct
21 Correct 108 ms 47412 KB Output is correct
22 Correct 104 ms 49860 KB Output is correct
23 Correct 71 ms 47300 KB Output is correct
24 Correct 244 ms 63312 KB Output is correct
25 Correct 184 ms 58408 KB Output is correct
26 Correct 205 ms 61064 KB Output is correct
27 Correct 268 ms 62288 KB Output is correct