oj.uz

Submission #163203

# Submission time Handle Problem Language Result Execution time Memory
163203 2019-11-11T18:06:48 Z TadijaSebez 마스코트 (JOI13_mascots) C++11
100 / 100
 520 ms 107360 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3050;
const int mod=1e9+7;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int X1,X2,Y1,Y2;
int dp[N][N],F[N*N],I[N*N];
int binom(int n, int k){ return mul(F[n],mul(I[k],I[n-k]));}
int main()
{
	int r,c,n;
	scanf("%i %i",&r,&c);
	scanf("%i",&n);
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%i %i",&x,&y);
		if(i==1) X1=X2=x,Y1=Y2=y;
		X1=min(X1,x);
		X2=max(X2,x);
		Y1=min(Y1,y);
		Y2=max(Y2,y);
	}
	int a=X2-X1+1,b=Y2-Y1+1;
	F[0]=1;for(int i=1;i<N*N;i++) F[i]=mul(F[i-1],i);
	I[0]=I[1]=1;for(int i=2;i<N*N;i++) I[i]=mod-mul(mod/i,I[mod%i]);
	for(int i=1;i<N*N;i++) I[i]=mul(I[i],I[i-1]);
	dp[a][b]=F[a*b-n];
	for(int i=a;i<=r;i++)
		for(int j=b;j<=c;j++) if(i!=a || j!=b)
			dp[i][j]=add(mul(dp[i-1][j],F[j]),mul(dp[i][j-1],F[i]));
	printf("%i\n",mul(dp[r][c],mul(binom(r-a,X1-1),binom(c-b,Y1-1))));
	return 0;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&r,&c);
  ~~~~~^~~~~~~~~~~~~~~
mascots.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
mascots.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 73068 KB Output is correct
2 Correct 418 ms 73320 KB Output is correct
3 Correct 433 ms 73068 KB Output is correct
4 Correct 403 ms 73268 KB Output is correct
5 Correct 399 ms 73200 KB Output is correct
6 Correct 396 ms 73164 KB Output is correct
7 Correct 391 ms 73252 KB Output is correct
8 Correct 389 ms 73280 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 73316 KB Output is correct
2 Correct 399 ms 73196 KB Output is correct
3 Correct 394 ms 73124 KB Output is correct
4 Correct 427 ms 73240 KB Output is correct
5 Correct 369 ms 73172 KB Output is correct
6 Correct 408 ms 73188 KB Output is correct
7 Correct 381 ms 73168 KB Output is correct
8 Correct 382 ms 73084 KB Output is correct
9 Correct 403 ms 73336 KB Output is correct
10 Correct 394 ms 73224 KB Output is correct
11 Correct 397 ms 73160 KB Output is correct
12 Correct 399 ms 73120 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 73284 KB Output is correct
2 Correct 419 ms 73664 KB Output is correct
3 Correct 389 ms 74360 KB Output is correct
4 Correct 395 ms 79368 KB Output is correct
5 Correct 411 ms 78480 KB Output is correct
6 Correct 431 ms 77744 KB Output is correct
7 Correct 385 ms 74184 KB Output is correct
8 Correct 382 ms 73228 KB Output is correct
9 Correct 412 ms 73784 KB Output is correct
10 Correct 499 ms 106704 KB Output is correct
11 Correct 482 ms 95856 KB Output is correct
12 Correct 442 ms 73848 KB Output is correct
13 Correct 392 ms 74640 KB Output is correct
14 Correct 398 ms 73208 KB Output is correct
15 Correct 512 ms 107360 KB Output is correct
16 Correct 482 ms 98352 KB Output is correct
17 Correct 425 ms 77176 KB Output is correct
18 Correct 520 ms 106048 KB Output is correct