Submission #472798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472798	2021-09-14T10:46:49 Z	prvocislo	Tents (JOI18_tents)	C++17	100 / 100	268 ms	63312 KB

tents

#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;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	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

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	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