| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 12943 |
2015-01-21T07:03:05 Z |
model_code |
마스코트 (JOI13_mascots) |
C++ |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
