Submission #485125

#	Time	Username	Problem	Language	Result	Execution time	Memory
485125		CSQ31	Tents (JOI18_tents)	C++17	48 / 100	152 ms	94216 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define MOD (ll)(1e9+7)
typedef long long int ll;
//each row <=2
//each col <=2
//cant have triangle
inline void mod(ll &x){
	if(x>=MOD)x-=MOD;
}
ll dp[2][301][301];
ll C[3001][3001];
int main()
{
	dp[0][0][0] = 1;
	for(int i=0;i<=3000;i++){
		for(int j=C[i][0] = 1;j<=i;j++){
			C[i][j] = C[i-1][j-1] + C[i-1][j];
			mod(C[i][j]);		
		}
	}
	int h,w;
	cin>>h>>w;
	for(int i=0;i<h;i++){
		for(int j=0;j<=w;j++){ //bad col
			for(int k=0;k<=w;k++){ //occu col
				if(!dp[0][j][k])continue;
				int emp = w-k-j;
				
				if(k){//place a single on occu and increase bad col by 1
					dp[1][j+1][k-1] += dp[0][j][k] * k %MOD;
					mod(dp[1][j+1][k-1]);
				}
				if(emp){
					//place a single on emp but its not faced south then increase bad col by 1
					dp[1][j+1][k] += dp[0][j][k] * 3 * emp%MOD;
					mod(dp[1][j+1][k]);
					//place a single on emp but its faced south then increase occu col by 1
					dp[1][j][k+1] += dp[0][j][k] * emp%MOD;
					mod(dp[1][j][k+1]);
				}
				if(emp>=2){//place two on emp and increase bad col by 2
					dp[1][j+2][k] += dp[0][j][k] * 1LL * C[emp][2]%MOD;
					dp[1][j+2][k]%=MOD;
				}
				dp[1][j][k]+=dp[0][j][k];
				mod(dp[1][j][k]);//do nothing
			}
		}
		for(int j=0;j<=w;j++){
			for(int k=0;k<=w;k++){
				dp[0][j][k] = dp[1][j][k];
				dp[1][j][k] = 0;
			}
		}
	} 	
	ll ans = 0;
	for(int i=0;i<=w;i++){
		for(int j=0;j<=w;j++){
			//cout<<i<<" "<<j<<" "<<dp[0][i][j]<<'\n';
			ans+=dp[0][i][j];
			mod(ans);	
		}
	}
	ans+=MOD-1;
	mod(ans);
	
	cout<<ans;
	
}

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