Submission #836638

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
836638	2023-08-24T13:37:07 Z	NK_	Tents (JOI18_tents)	C++17	100 / 100	97 ms	70824 KB

tents

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int H, W; cin >> H >> W; 

	V<vl> dp(H+1, vl(W+1, 0));
	for(int r = 0; r <= H; r++) for(int c = 0; c <= W; c++) {
		if (r == 0 || c == 0) dp[r][c] = 1;
		else {
			dp[r][c] = (dp[r-1][c] + dp[r-1][c-1] * 4LL * c) % MOD;

			if (r >= 2) {
				dp[r][c] += (dp[r-2][c-1] * (r - 1) * 1LL * c) % MOD;
				dp[r][c] %= MOD;
			}

			if (c >= 2) {
				dp[r][c] += (dp[r-1][c-2] * (c * 1LL * (c - 1)) / 2) % MOD;
				dp[r][c] %= MOD;
			}
		}
	}
	
	dp[H][W] -= 1;
	cout << (dp[H][W] + MOD) % MOD << nl;

	exit(0-0);
} 	

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	2 ms	980 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	596 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	2 ms	980 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	61 ms	44200 KB	Output is correct
16	Correct	5 ms	3156 KB	Output is correct
17	Correct	14 ms	10068 KB	Output is correct
18	Correct	18 ms	12520 KB	Output is correct
19	Correct	70 ms	51412 KB	Output is correct
20	Correct	73 ms	41196 KB	Output is correct
21	Correct	38 ms	27220 KB	Output is correct
22	Correct	38 ms	26836 KB	Output is correct
23	Correct	21 ms	15096 KB	Output is correct
24	Correct	97 ms	70824 KB	Output is correct
25	Correct	76 ms	52664 KB	Output is correct
26	Correct	82 ms	60344 KB	Output is correct
27	Correct	94 ms	68164 KB	Output is correct