Submission #1277971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277971		WH8	Tents (JOI18_tents)	C++20	100 / 100	227 ms	71484 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define int long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
vector<vector<int>> mem(3005, vector<int>(3005, -1));
int h,w;
const int m=1000000007;
int dp(int c, int e){
	if(c>=w or e<=0)return 1;
	if(mem[c][e]!=-1)return mem[c][e];
	return mem[c][e]=(dp(c+1, e)+4*e%m*dp(c+1, e-1)%m+e*(e-1)/2%m*dp(c+1, e-2)%m+(w-c-1)*e%m*dp(c+2, e-1)%m)%m;
}
signed main(){
	cin>>h>>w;
	cout<<dp(0, h)-1;
}
	

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