Submission #794565

#	Time	Username	Problem	Language	Result	Execution time	Memory
794565		Sandarach151	Tents (JOI18_tents)	C++17	100 / 100	56 ms	70688 KiB

tents

#include<bits/stdc++.h>
using namespace std;

const long long MODD = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long h, w;
	cin >> h >> w;
	long long ans[h+1][w+1];
	for(long long i=0; i<=h; i++){
		ans[i][0]=1;
	}
	for(long long i=0; i<=w; i++){
		ans[0][i]=1;
	}
	for(long long i=1; i<=h; i++){
		ans[i][1]=i*4+i*(i-1)/2+1;
	}
	for(long long i=1; i<=w; i++){
		ans[1][i]=i*4+i*(i-1)/2+1;
	}
	for(long long i=2; i<=h; i++){
		for(long long j=2; j<=w; j++){
			long long caseEWN = 3*j*ans[i-1][j-1];
			long long caseSs = j*ans[i-1][j-1];
			long long caseSd = j*(i-1)*ans[i-2][j-1];
			ans[i][j]=ans[i-1][j]+j*(j-1)/2*ans[i-1][j-2]+caseEWN+caseSs+caseSd;
			ans[i][j] %= MODD;
		}
	}
	cout << ans[h][w]-1 << '\n';
	return 0;
}

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