Submission #995294

#	Time	Username	Problem	Language	Result	Execution time	Memory
995294		vako_p	Tents (JOI18_tents)	C++14	100 / 100	71 ms	70996 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 3e3 + 5;
ll n,m,mod = 1e9 + 7,dp[mxN][mxN],pw;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// 0 -- n 1 -- s 2 -- e 3 -- w
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		dp[1][i] = (4 + pw + dp[1][i - 1]) % mod;
		pw++;
	}	
	for(int i = 1; i <= m; i++) dp[1][i] = (dp[1][i] + 1) % mod;
	for(int i = 0; i <= n; i++) dp[i][0] = 1;
	for(int i = 0; i <= m; i++) dp[0][i] = 1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = (dp[i - 1][j - 1] * 4 + dp[i - 2][j - 1] * (i - 1)) % mod;
			if(j > 1) dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * (j - 1) + (i - 1) * (j - 1) * dp[i - 1][j - 2]) % mod;
			dp[i][j] = (dp[i][j] + dp[i][j - 1] + dp[i - 1][j - 1] * (i - 1) * 4 + dp[i - 2][j - 1] * (i - 1) * (i - 2) / 2) % mod;		
		}
	}
	cout << (dp[n][m] - 1 + mod) % mod;
}

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