답안 #995294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995294	2024-06-08T19:19:37 Z	vako_p	Tents (JOI18_tents)	C++14	100 / 100	71 ms	70996 KB

tents

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 3e3 + 5;
ll n,m,mod = 1e9 + 7,dp[mxN][mxN],pw;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// 0 -- n 1 -- s 2 -- e 3 -- w
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		dp[1][i] = (4 + pw + dp[1][i - 1]) % mod;
		pw++;
	}	
	for(int i = 1; i <= m; i++) dp[1][i] = (dp[1][i] + 1) % mod;
	for(int i = 0; i <= n; i++) dp[i][0] = 1;
	for(int i = 0; i <= m; i++) dp[0][i] = 1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = (dp[i - 1][j - 1] * 4 + dp[i - 2][j - 1] * (i - 1)) % mod;
			if(j > 1) dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * (j - 1) + (i - 1) * (j - 1) * dp[i - 1][j - 2]) % mod;
			dp[i][j] = (dp[i][j] + dp[i][j - 1] + dp[i - 1][j - 1] * (i - 1) * 4 + dp[i - 2][j - 1] * (i - 1) * (i - 2) / 2) % mod;		
		}
	}
	cout << (dp[n][m] - 1 + mod) % mod;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	0 ms	2392 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	0 ms	2392 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	6 ms	55644 KB	Output is correct
15	Correct	47 ms	66260 KB	Output is correct
16	Correct	3 ms	6492 KB	Output is correct
17	Correct	11 ms	17012 KB	Output is correct
18	Correct	14 ms	29304 KB	Output is correct
19	Correct	51 ms	70232 KB	Output is correct
20	Correct	44 ms	57948 KB	Output is correct
21	Correct	28 ms	39512 KB	Output is correct
22	Correct	29 ms	51804 KB	Output is correct
23	Correct	20 ms	70404 KB	Output is correct
24	Correct	71 ms	70996 KB	Output is correct
25	Correct	52 ms	62296 KB	Output is correct
26	Correct	59 ms	68188 KB	Output is correct
27	Correct	69 ms	70236 KB	Output is correct