Submission #485125

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
485125	2021-11-06T09:48:50 Z	CSQ31	Tents (JOI18_tents)	C++17	48 / 100	152 ms	94216 KB

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.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	46636 KB	Output is correct
2	Correct	41 ms	47404 KB	Output is correct
3	Correct	39 ms	46464 KB	Output is correct
4	Correct	33 ms	46540 KB	Output is correct
5	Correct	41 ms	47740 KB	Output is correct
6	Correct	45 ms	46916 KB	Output is correct
7	Correct	43 ms	47516 KB	Output is correct
8	Correct	40 ms	46816 KB	Output is correct
9	Correct	33 ms	46580 KB	Output is correct
10	Correct	65 ms	47152 KB	Output is correct
11	Correct	36 ms	47968 KB	Output is correct
12	Correct	152 ms	47980 KB	Output is correct

Subtask #2

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	46636 KB	Output is correct
2	Correct	41 ms	47404 KB	Output is correct
3	Correct	39 ms	46464 KB	Output is correct
4	Correct	33 ms	46540 KB	Output is correct
5	Correct	41 ms	47740 KB	Output is correct
6	Correct	45 ms	46916 KB	Output is correct
7	Correct	43 ms	47516 KB	Output is correct
8	Correct	40 ms	46816 KB	Output is correct
9	Correct	33 ms	46580 KB	Output is correct
10	Correct	65 ms	47152 KB	Output is correct
11	Correct	36 ms	47968 KB	Output is correct
12	Correct	152 ms	47980 KB	Output is correct
13	Runtime error	91 ms	94216 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-