Submission #1033950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033950		vjudge1	Tents (JOI18_tents)	C++17	100 / 100	63 ms	70884 KiB

tents

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

long long dp[3008][3008];

long long C2(int x) {return (1LL * x * (x - 1) / 2) % mod;}

signed main() {
	int n, m; cin >> n >> m;
	for (int i = 0; i <= m; ++i) dp[0][i] = 1;
	for (int i = 0; i <= n; ++i) dp[i][0] = 1;
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) 
		dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1] * i * 4 + dp[i - 2][j - 1] * C2(i) + dp[i - 1][j - 2] * i * (j - 1)) % mod;
	cout << (dp[n][m] + mod -1 ) % mod;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52