답안 #948890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948890	2024-03-18T15:57:18 Z	starchan	Tents (JOI18_tents)	C++17	100 / 100	116 ms	71356 KB

tents

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int mod = 1e9+7;
int c2(int j)
{
	return ((j*(j-1))/2)%mod;
}
signed main()
{
	fast();
	int n, m;
	cin >> n >> m;
	int dp[n+10][m+10];
	for(int i = 0; i <= n+9; i++)
		dp[i][0] = 1;
	for(int i = 0; i <= m+9; i++)
		dp[0][i] = 1;
	for(int i = 1; i <= n+9; i++)
		dp[i][1] = (1 + (4*i) + c2(i))%mod;
	for(int i = 1; i <= m+9; i++)
		dp[1][i] = (1 + (4*i) + c2(i))%mod;
	for(int i = 2; i <= n+9; i++)
	{
		for(int j = 2; j <= m+9; j++)
		{
			dp[i][j] = ((dp[i-1][j]%mod)+((4*j*dp[i-1][j-1])%mod)+(c2(j)*dp[i-1][j-2])%mod)%mod;
			dp[i][j]+=(((i-1)*j*dp[i-2][j-1])%mod); dp[i][j]%=mod;
		}
	}
	dp[n][m]+=(mod-1);
	dp[n][m]%=mod;
	cout << dp[n][m] << "\n";
	return 0;
}	

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	964 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	0 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	2 ms	964 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	452 KB	Output is correct
15	Correct	73 ms	44412 KB	Output is correct
16	Correct	5 ms	3164 KB	Output is correct
17	Correct	17 ms	10332 KB	Output is correct
18	Correct	20 ms	12772 KB	Output is correct
19	Correct	84 ms	51832 KB	Output is correct
20	Correct	66 ms	41564 KB	Output is correct
21	Correct	46 ms	27484 KB	Output is correct
22	Correct	45 ms	27096 KB	Output is correct
23	Correct	25 ms	15196 KB	Output is correct
24	Correct	116 ms	71356 KB	Output is correct
25	Correct	85 ms	52984 KB	Output is correct
26	Correct	98 ms	60772 KB	Output is correct
27	Correct	111 ms	68588 KB	Output is correct