Submission #307046

#	Time	Username	Problem	Language	Result	Execution time	Memory
307046		nafis_shifat	Tents (JOI18_tents)	C++14	100 / 100	194 ms	70776 KiB

tents

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
const ll mod=1e9+7;
ll nc2(ll n) {
	ll res= n * (n-1) /2  % mod;
	
	return res % mod;
}
int main() {
	int h,w;
	cin>>h>>w;


	ll dp[h+1][w+1];
	

	for(int i=1;i<=w;i++) {
		dp[1][i] = ( 4 * i + nc2(i) + 1) % mod ;
		dp[0][i]=1;
	}

	for(int i=1;i<=h;i++) {
		dp[i][1] = ( 4 * i + nc2(i) + 1)  % mod;
		dp[i][0]=1;
	}

	

	


	

	
	for(int i=2;i<=h;i++) {
		for(int j=2;j<=w;j++) {
			dp[i][j] = 4 * j * dp[i-1][j-1] % mod;

			//cout<<dp[i][j]<<endl;

			dp[i][j] += nc2(j) * dp[i-1][j-2] % mod;
			dp[i][j] %= mod;
			//cout<<dp[i][j]<<endl;

			dp[i][j] += (j * (i-1) % mod) * dp[i-2][j-1] % mod;
			dp[i][j] %= mod;
			

			dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
			

		}
	}

	cout<<(dp[h][w] - 1 + mod) % mod<<endl;
}

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