Submission #66988

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
66988	2018-08-13T06:59:31 Z	Diuven	Tents (JOI18_tents)	C++11	48 / 100	2000 ms	28556 KB

tents

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-