Submission #93633

# Submission time Handle Problem Language Result Execution time Memory
93633 2019-01-10T13:06:53 Z kjain_1810 Tents (JOI18_tents) C++17
100 / 100
192 ms 70904 KB
#include <bits/stdc++.h>
using namespace std;
 
int n, m;
long long dp[3007][3007];
const long long mod = 1e9 + 7;
 
int main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0; i <= m; i++) dp[0][i] = 1;
	for(int i = 0; i <= n; i++) dp[i][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = (dp[i - 1][j] + 4LL * j * dp[i - 1][j - 1]) % mod;
			if(i >= 2) dp[i][j] = (dp[i][j] + 1LL * (i - 1) * j * dp[i - 2][j - 1]) % mod;
			if(j >= 2) dp[i][j] = (dp[i][j] + 1LL * j * (j - 1) / 2LL * dp[i - 1][j - 2]) % mod;
		}
	}
	dp[n][m] = (dp[n][m] - 1 + mod) % mod;
	cout << dp[n][m];
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 1144 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 1784 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 2296 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 1144 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 2 ms 888 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 1784 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 4 ms 2296 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 9 ms 9720 KB Output is correct
15 Correct 80 ms 55288 KB Output is correct
16 Correct 7 ms 4092 KB Output is correct
17 Correct 22 ms 12932 KB Output is correct
18 Correct 27 ms 17144 KB Output is correct
19 Correct 100 ms 62968 KB Output is correct
20 Correct 81 ms 50860 KB Output is correct
21 Correct 54 ms 33784 KB Output is correct
22 Correct 56 ms 35480 KB Output is correct
23 Correct 37 ms 27128 KB Output is correct
24 Correct 116 ms 70904 KB Output is correct
25 Correct 192 ms 61304 KB Output is correct
26 Correct 114 ms 66680 KB Output is correct
27 Correct 113 ms 69112 KB Output is correct