oj.uz

답안 #12943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12943 2015-01-21T07:03:05 Z model_code 마스코트 (JOI13_mascots) C++
100 / 100
 576 ms 235604 KB 
#include <cstdio>

int MOD=1000000007;
int R,C,N;
int r1,r2,c1,c2;
long long fact[12000001];
long long dp[3002][3002];
long long comb[3001][3001];
int main() {
	scanf("%d%d%d",&R,&C,&N);
	r1=R; c1=C;
	for(int i=0;i<N;i++) {
		int kr,kc;
		scanf("%d%d",&kr,&kc);
		if(r1>kr) r1=kr;
		if(r2<kr) r2=kr;
		if(c1>kc) c1=kc;
		if(c2<kc) c2=kc;
	}
	fact[0]=1;
	for(int i=1;i<12000001;i++) fact[i]=(fact[i-1]*i)%MOD;
	comb[0][0]=1;
	for(int i=1;i<3001;i++) {
		comb[i][0]=comb[i-1][0];
		for(int j=1;j<=i;j++) {
			comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%MOD;
		}
	}
	dp[0][0]=fact[(r2-r1+1)*(c2-c1+1)-N];
	for(int i=0;i<=R-(r2-r1+1);i++) {
		for(int j=0;j<=C-(c2-c1+1);j++) {
			dp[i+1][j]=(dp[i+1][j]+dp[i][j]*fact[C-j])%MOD;
			dp[i][j+1]=(dp[i][j+1]+dp[i][j]*fact[R-i])%MOD;
		}
	}
	long long sol=dp[R-(r2-r1+1)][C-(c2-c1+1)];
	sol=(sol*comb[R-(r2-r1+1)][r1-1])%MOD;
	sol=(sol*comb[C-(c2-c1+1)][c1-1])%MOD;
	printf("%lld\n",sol);
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 304 ms 235604 KB Output is correct
2 Correct 328 ms 235604 KB Output is correct
3 Correct 340 ms 235604 KB Output is correct
4 Correct 336 ms 235604 KB Output is correct
5 Correct 324 ms 235604 KB Output is correct
6 Correct 292 ms 235604 KB Output is correct
7 Correct 332 ms 235604 KB Output is correct
8 Correct 352 ms 235604 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 332 ms 235604 KB Output is correct
2 Correct 320 ms 235604 KB Output is correct
3 Correct 332 ms 235604 KB Output is correct
4 Correct 316 ms 235604 KB Output is correct
5 Correct 312 ms 235604 KB Output is correct
6 Correct 340 ms 235604 KB Output is correct
7 Correct 344 ms 235604 KB Output is correct
8 Correct 344 ms 235604 KB Output is correct
9 Correct 332 ms 235604 KB Output is correct
10 Correct 304 ms 235604 KB Output is correct
11 Correct 312 ms 235604 KB Output is correct
12 Correct 328 ms 235604 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 235604 KB Output is correct
2 Correct 316 ms 235604 KB Output is correct
3 Correct 328 ms 235604 KB Output is correct
4 Correct 348 ms 235604 KB Output is correct
5 Correct 352 ms 235604 KB Output is correct
6 Correct 336 ms 235604 KB Output is correct
7 Correct 336 ms 235604 KB Output is correct
8 Correct 312 ms 235604 KB Output is correct
9 Correct 328 ms 235604 KB Output is correct
10 Correct 556 ms 235604 KB Output is correct
11 Correct 448 ms 235604 KB Output is correct
12 Correct 360 ms 235604 KB Output is correct
13 Correct 324 ms 235604 KB Output is correct
14 Correct 324 ms 235604 KB Output is correct
15 Correct 576 ms 235604 KB Output is correct
16 Correct 496 ms 235604 KB Output is correct
17 Correct 360 ms 235604 KB Output is correct
18 Correct 548 ms 235604 KB Output is correct