Submission #163203

#	Time	Username	Problem	Language	Result	Execution time	Memory
163203		TadijaSebez	마스코트 (JOI13_mascots)	C++11	100 / 100	520 ms	107360 KiB

mascots

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60