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

tents

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

Subtask #1

48.0 / 48.0

#	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

Subtask #2

52.0 / 52.0

#	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