Submission #751710

# Submission time Handle Problem Language Result Execution time Memory
751710 2023-06-01T10:12:14 Z Dan4Life Tents (JOI18_tents) C++17
100 / 100
63 ms 71036 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxN = (int)3e3+10;
const int MOD = (int)1e9+7;
int n, m, dp[mxN][mxN];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m; // rows and cols can be separated
	for(int i = 0; i < mxN; i++) dp[i][0]=dp[0][i]=1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] += dp[i-1][j]; // empty row
			dp[i][j] += 4*j*dp[i-1][j-1]; // exactly 1 on row
			if(j>1) dp[i][j] += (j-1)*j/2*dp[i-1][j-2]; // exactly 2 on row
			if(i>1) dp[i][j] += j*(i-1) * dp[i-2][j-1]; //1 on both row and col
			dp[i][j]%=MOD;
		}
	}
	cout << (dp[n][m]+MOD-1)%MOD << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 5 ms 12440 KB Output is correct
4 Correct 7 ms 12500 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12588 KB Output is correct
7 Correct 6 ms 12628 KB Output is correct
8 Correct 6 ms 12628 KB Output is correct
9 Correct 5 ms 12500 KB Output is correct
10 Correct 6 ms 12724 KB Output is correct
11 Correct 5 ms 12500 KB Output is correct
12 Correct 6 ms 13140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 6 ms 12500 KB Output is correct
3 Correct 5 ms 12440 KB Output is correct
4 Correct 7 ms 12500 KB Output is correct
5 Correct 5 ms 12628 KB Output is correct
6 Correct 6 ms 12588 KB Output is correct
7 Correct 6 ms 12628 KB Output is correct
8 Correct 6 ms 12628 KB Output is correct
9 Correct 5 ms 12500 KB Output is correct
10 Correct 6 ms 12724 KB Output is correct
11 Correct 5 ms 12500 KB Output is correct
12 Correct 6 ms 13140 KB Output is correct
13 Correct 6 ms 12500 KB Output is correct
14 Correct 6 ms 12500 KB Output is correct
15 Correct 48 ms 56160 KB Output is correct
16 Correct 8 ms 15316 KB Output is correct
17 Correct 15 ms 22228 KB Output is correct
18 Correct 16 ms 24532 KB Output is correct
19 Correct 50 ms 63308 KB Output is correct
20 Correct 42 ms 53076 KB Output is correct
21 Correct 32 ms 39248 KB Output is correct
22 Correct 34 ms 38860 KB Output is correct
23 Correct 19 ms 27092 KB Output is correct
24 Correct 63 ms 71036 KB Output is correct
25 Correct 55 ms 63024 KB Output is correct
26 Correct 59 ms 67540 KB Output is correct
27 Correct 62 ms 69524 KB Output is correct