제출 #43978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43978		MatheusLealV	Tents (JOI18_tents)	C++17	100 / 100	314 ms	72800 KiB

tents

#include <bits/stdc++.h>
#define N 3030
#define mod (1000000007)
using namespace std;
typedef long long ll;

ll H, W, dp[N][N];

ll solve(int lf, int cf)
{
	if(lf < 0 || cf < 0) return 0;

	if(!lf || !cf) return 1;

	if(dp[lf][cf] != -1) return dp[lf][cf];

	ll nao_coloca = solve(lf - 1, cf), coloca1 = solve(lf - 1, cf - 1)*4*cf;

	ll coloca2 = solve(lf - 1, cf - 2)*cf*(cf - 1)/2, coloca2row = solve(lf - 2, cf - 1)*cf*(lf - 1);

	return dp[lf][cf] = (nao_coloca + coloca1 + coloca2 + coloca2row)%mod;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>H>>W;

	memset(dp, -1, sizeof dp);

	cout<<(solve(H, W) + mod - 1)%mod<<"\n";
}

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