답안 #331680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331680	2020-11-29T13:48:22 Z	Blagojce	Tents (JOI18_tents)	C++11	100 / 100	82 ms	70764 KB

tents

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 2e18;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 5e5;
mt19937 _rand(time(NULL));
clock_t z;

int main(){
	int n, m;
	cin >> n >> m;
	ll dp[n+1][m+1];
	memset(dp, 0, sizeof(dp));
	fr(i, 0, n+1) dp[i][0] = 1;
	fr(i, 0, m+1) dp[0][i] = 1;
	
	fr(i, 1, n+1){
		fr(j, 1, m+1){
			dp[i][j] = dp[i-1][j];
			if(j >= 2) dp[i][j] += dp[i-1][j-2]*j*(j-1)/2;
			if(i >= 2) dp[i][j] += dp[i-2][j-1]*j*(i-1);
			dp[i][j] += j*dp[i-1][j-1]*4;
			dp[i][j] %= mod;
		}
	}
	ll ans = (dp[n][m]-1+mod)%mod;
	cout<<ans<<endl;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	2 ms	1024 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	2 ms	1024 KB	Output is correct
13	Correct	1 ms	492 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	52 ms	44152 KB	Output is correct
16	Correct	4 ms	3180 KB	Output is correct
17	Correct	12 ms	10092 KB	Output is correct
18	Correct	17 ms	12396 KB	Output is correct
19	Correct	59 ms	51308 KB	Output is correct
20	Correct	47 ms	41196 KB	Output is correct
21	Correct	39 ms	27244 KB	Output is correct
22	Correct	32 ms	26932 KB	Output is correct
23	Correct	19 ms	14956 KB	Output is correct
24	Correct	82 ms	70764 KB	Output is correct
25	Correct	60 ms	52588 KB	Output is correct
26	Correct	78 ms	60396 KB	Output is correct
27	Correct	78 ms	68096 KB	Output is correct