Submission #485263

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485263	2021-11-06T19:34:42 Z	CSQ31	Tents (JOI18_tents)	C++17	100 / 100	337 ms	71000 KB

tents

#include <bits/stdc++.h>
using namespace std;
#define MOD (ll)(1e9+7)
typedef long long int ll;
//each row <=2
//each col <=2
//cant have triangle
inline void mod(ll &x){
	if(x>=MOD)x-=MOD;
}
ll eval(ll x){
	return (x*(x-1))/2 %MOD;
}
ll dp[3001][3001];
ll solve(int h,int w){
	if(dp[h][w]!=-1)return dp[h][w];
	if(!h || !w)return 1;
	ll res = solve(h-1,w); //empty row
	res+=(solve(h-1,w-1) * 4LL * w %MOD); //single tent in a col
	mod(res);
	if(w>=2)res+=solve(h-1,w-2) * eval(w) %MOD;//two tents same row
	mod(res);
	if(h>=2)res+=(solve(h-2,w-1) * (h-1) %MOD) * w%MOD; //two tents same col
	mod(res);
	dp[h][w] = res;
	//cout<<h<<" "<<w<<" "<<res<<'\n';
	return res;
}
int main()
{
	int h,w;
	cin>>h>>w;
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++)dp[i][j] = -1;
		
	cout<<(solve(h,w)+MOD-1)%MOD;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	2 ms	1356 KB	Output is correct
7	Correct	1 ms	808 KB	Output is correct
8	Correct	1 ms	1356 KB	Output is correct
9	Correct	1 ms	716 KB	Output is correct
10	Correct	2 ms	1740 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	4 ms	2124 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	2 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	2 ms	1356 KB	Output is correct
7	Correct	1 ms	808 KB	Output is correct
8	Correct	1 ms	1356 KB	Output is correct
9	Correct	1 ms	716 KB	Output is correct
10	Correct	2 ms	1740 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	4 ms	2124 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	4 ms	9804 KB	Output is correct
15	Correct	238 ms	55376 KB	Output is correct
16	Correct	4 ms	4012 KB	Output is correct
17	Correct	26 ms	12840 KB	Output is correct
18	Correct	53 ms	17072 KB	Output is correct
19	Correct	260 ms	63200 KB	Output is correct
20	Correct	229 ms	50984 KB	Output is correct
21	Correct	115 ms	34032 KB	Output is correct
22	Correct	133 ms	35532 KB	Output is correct
23	Correct	86 ms	27172 KB	Output is correct
24	Correct	337 ms	71000 KB	Output is correct
25	Correct	254 ms	61348 KB	Output is correct
26	Correct	290 ms	66748 KB	Output is correct
27	Correct	326 ms	69132 KB	Output is correct