oj.uz

답안 #485125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485125 2021-11-06T09:48:50 Z CSQ31 Tents (JOI18_tents) C++17
48 / 100
 152 ms 94216 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -