oj.uz

답안 #717012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
717012 2023-03-31T20:56:30 Z AmirAli_H1 Tents (JOI18_tents) C++17
100 / 100
 108 ms 70880 KB 
// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef long long int	ll;
typedef long double	ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;

#define all(x)		(x).begin(),(x).end()
#define len(x)		((ll) (x).size())
#define F		first
#define S		second
#define pb		push_back
#define sep             ' '
#define endl            '\n'
#define Mp		make_pair
#define debug(x)	cerr << #x << ": " <<  x << endl;
#define kill(x)		cout << x << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define file_io(x,y)	freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
const int maxn = 3000 + 4;
const int mod = 1e9 + 7;
ll dp[maxn][maxn];

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

Subtask #1
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 1348 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 1736 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 2244 KB Output is correct

Subtask #2
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 1348 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 1364 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 1736 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 2244 KB Output is correct
13 Correct 1 ms 324 KB Output is correct
14 Correct 4 ms 9556 KB Output is correct
15 Correct 76 ms 55244 KB Output is correct
16 Correct 5 ms 4052 KB Output is correct
17 Correct 17 ms 12884 KB Output is correct
18 Correct 22 ms 16980 KB Output is correct
19 Correct 81 ms 62940 KB Output is correct
20 Correct 65 ms 50904 KB Output is correct
21 Correct 43 ms 33748 KB Output is correct
22 Correct 53 ms 35404 KB Output is correct
23 Correct 30 ms 27016 KB Output is correct
24 Correct 108 ms 70880 KB Output is correct
25 Correct 87 ms 61140 KB Output is correct
26 Correct 102 ms 66620 KB Output is correct
27 Correct 104 ms 68880 KB Output is correct