oj.uz

답안 #66988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66988 2018-08-13T06:59:31 Z Diuven Tents (JOI18_tents) C++11
48 / 100
 2000 ms 28556 KB 
#include <iostream>
using namespace std;
typedef long long ll;

const int MX=3010, MOD=1e9+7;

int h, w, C[MX][MX], F[2*MX], T[MX], U[2*MX];

int c(int n, int r){
	if(n<0 || r<0 || n<r) return 0;
	return C[n][r];
}

int f(int h, int w, int a){
	ll res=1;
	res=res*c(h,a)%MOD;
	res=res*c(w,2*a)%MOD;
	res=res*F[2*a]%MOD;
	res=res*T[a]%MOD;
	return res;
}
int g(int h, int w, int a){
	ll res=1;
	res=res*c(h,a)%MOD;
	res=res*c(w,a)%MOD;
	res=res*F[a]%MOD;
	res=res*U[2*a]%MOD;
	return res;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>h>>w;

	for(int i=0; i<MX; i++){
		C[i][0]=C[i][i]=1;
		for(int j=1; j<i; j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
	}
	F[0]=1;
	for(int i=1; i<2*MX; i++) F[i]=(1LL*F[i-1]*i)%MOD;
	T[0]=1, T[1]=5e8+4;
	for(int i=2; i<MX; i++) T[i]=(1LL*T[i-1]*T[1])%MOD;
	U[0]=1;
	for(int i=1; i<2*MX; i++) U[i]=U[i-1]*2%MOD;


	int ans=0;
	for(int a=0; a<=h; a++){
		for(int b=0; b<=w; b++){
			for(int c=0; c<=h; c++){
				if(a+b+c==0) continue;
				ll now=f(h, w, a);
				now=now*f(w-2*a, h-a, b)%MOD;
				now=now*g(h-a-2*b, w-2*a-b, c)%MOD;
				ans=(ans+now)%MOD;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 28156 KB Output is correct
2 Correct 39 ms 28264 KB Output is correct
3 Correct 29 ms 28264 KB Output is correct
4 Correct 37 ms 28288 KB Output is correct
5 Correct 79 ms 28436 KB Output is correct
6 Correct 224 ms 28440 KB Output is correct
7 Correct 122 ms 28472 KB Output is correct
8 Correct 218 ms 28472 KB Output is correct
9 Correct 42 ms 28472 KB Output is correct
10 Correct 559 ms 28516 KB Output is correct
11 Correct 35 ms 28516 KB Output is correct
12 Correct 1176 ms 28556 KB Output is correct

Subtask #2
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 28156 KB Output is correct
2 Correct 39 ms 28264 KB Output is correct
3 Correct 29 ms 28264 KB Output is correct
4 Correct 37 ms 28288 KB Output is correct
5 Correct 79 ms 28436 KB Output is correct
6 Correct 224 ms 28440 KB Output is correct
7 Correct 122 ms 28472 KB Output is correct
8 Correct 218 ms 28472 KB Output is correct
9 Correct 42 ms 28472 KB Output is correct
10 Correct 559 ms 28516 KB Output is correct
11 Correct 35 ms 28516 KB Output is correct
12 Correct 1176 ms 28556 KB Output is correct
13 Correct 36 ms 28556 KB Output is correct
14 Correct 712 ms 28556 KB Output is correct
15 Execution timed out 2076 ms 28556 KB Time limit exceeded
16 Halted 0 ms 0 KB -