Submission #24906

#	Time	Username	Problem	Language	Result	Execution time	Memory
24906		khsoo01	마스코트 (JOI13_mascots)	C++11	100 / 100	163 ms	142904 KiB

mascots

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll r, c, n, dt[3005][3005], fac[9000005], inv[3005];
ll xs = mod, xe = -mod, ys = mod, ye = -mod, w, h;

ll calc (ll X, ll Y) {
	if(!Y) return 1;
	ll ret = calc(X, Y/2);
	ret = ret * ret % mod;
	if(Y & 1) ret = ret * X % mod;
	return ret;
}

ll com (ll X, ll Y) {
	return fac[X] * inv[Y] % mod * inv[X-Y] % mod;
}

int main()
{
	scanf("%lld%lld%lld",&r,&c,&n);
	for(ll i=1;i<=n;i++) {
		ll X, Y;
		scanf("%lld%lld",&X,&Y);
		xs = min(X, xs); xe = max(X, xe);
		ys = min(Y, ys); ye = max(Y, ye);
	}
	fac[0] = 1; inv[0] = 1;
	for(ll i=1;i<=r*c;i++) {
		fac[i] = fac[i-1] * i % mod;
	}
	for(ll i=1;i<=max(r,c);i++) {
		inv[i] = calc(fac[i], mod-2);
	}
	w = xe - xs + 1;
	h = ye - ys + 1;
	dt[w][h] = fac[w*h-n];
	for(ll i=w;i<=r;i++) for(ll j=h;j<=c;j++) {
		dt[i][j] = (dt[i][j] + dt[i-1][j] * fac[j] + dt[i][j-1] * fac[i]) % mod;
	}
	printf("%lld\n",dt[r][c] * com(r-w, xs-1) % mod * com(c-h, ys-1) % mod);
}

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&r,&c,&n);
                                ^
mascots.cpp:25:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&X,&Y);
                          ^

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60