답안 #386973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386973	2021-04-07T17:51:23 Z	wind_reaper	Tents (JOI18_tents)	C++17	100 / 100	517 ms	71276 KB

tents

#include <bits/stdc++.h>

using namespace std;

const int64_t mod = 1000000007;

int64_t dp[3001][3001];

int64_t f(int64_t row, int64_t col){
	if(row < 0 || col < 0)
		return 0;
	if(row == 0 || col == 0) return 1;
	if(dp[row][col] != -1)
		return dp[row][col];
	
	int64_t val = f(row, col-1);
	(val += row*4*f(row-1, col-1)) %= mod;
	(val += row*(col-1)*f(row-1, col-2)) %= mod;
	(val += row*(row-1)/2*f(row-2, col-1)) %= mod;

	return dp[row][col] = val;
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int h, w;
	cin >> h >> w;

	memset(dp, -1, sizeof dp);

	cout << (f(h, w) - 1 + mod) % mod << '\n';

	return 0; 
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	70892 KB	Output is correct
2	Correct	39 ms	70892 KB	Output is correct
3	Correct	39 ms	70912 KB	Output is correct
4	Correct	38 ms	70892 KB	Output is correct
5	Correct	38 ms	70892 KB	Output is correct
6	Correct	39 ms	70892 KB	Output is correct
7	Correct	39 ms	70892 KB	Output is correct
8	Correct	39 ms	70892 KB	Output is correct
9	Correct	39 ms	70892 KB	Output is correct
10	Correct	39 ms	70892 KB	Output is correct
11	Correct	38 ms	70892 KB	Output is correct
12	Correct	40 ms	70892 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	70892 KB	Output is correct
2	Correct	39 ms	70892 KB	Output is correct
3	Correct	39 ms	70912 KB	Output is correct
4	Correct	38 ms	70892 KB	Output is correct
5	Correct	38 ms	70892 KB	Output is correct
6	Correct	39 ms	70892 KB	Output is correct
7	Correct	39 ms	70892 KB	Output is correct
8	Correct	39 ms	70892 KB	Output is correct
9	Correct	39 ms	70892 KB	Output is correct
10	Correct	39 ms	70892 KB	Output is correct
11	Correct	38 ms	70892 KB	Output is correct
12	Correct	40 ms	70892 KB	Output is correct
13	Correct	39 ms	71020 KB	Output is correct
14	Correct	39 ms	70800 KB	Output is correct
15	Correct	302 ms	71020 KB	Output is correct
16	Correct	50 ms	71020 KB	Output is correct
17	Correct	82 ms	71020 KB	Output is correct
18	Correct	91 ms	71020 KB	Output is correct
19	Correct	349 ms	71148 KB	Output is correct
20	Correct	291 ms	71020 KB	Output is correct
21	Correct	213 ms	71276 KB	Output is correct
22	Correct	178 ms	71020 KB	Output is correct
23	Correct	54 ms	70892 KB	Output is correct
24	Correct	517 ms	71276 KB	Output is correct
25	Correct	394 ms	71020 KB	Output is correct
26	Correct	448 ms	71148 KB	Output is correct
27	Correct	508 ms	71276 KB	Output is correct