Submission #108913

#	Time	Username	Problem	Language	Result	Execution time	Memory
108913		njchung99	마스코트 (JOI13_mascots)	C++14	100 / 100	338 ms	147300 KiB

mascots

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define mod  1000000007
using namespace std;
ll n, m,k;
ll dp[3100][3100];
ll fac[9000010];
ll func(ll x, ll y) {
	if (x == n && y == m)return 1;
	if (x > n||y > m)return 0;
	ll &ret = dp[x][y];
	if (ret != -1)return ret;
	ret = 0;
	ret += ((func(x + 1, y)*fac[y]) % mod);
	ret += ((func(x, y+1)*fac[x]) % mod);
	ret %= mod;
	return ret;
}
ll mypow(ll a, ll b) {
	if (b == 0)return 1;
	if (b % 2)
		return (a*mypow((a*a) % mod, b / 2)) % mod;
	else
		return mypow((a*a) % mod, b / 2);
}
ll comb(ll a, ll b) {
	ll gap = fac[a];
	gap *= mypow(fac[b], mod - 2);
	gap %= mod;
	gap *= mypow(fac[a - b], mod - 2);
	gap %= mod;
	return gap;
}
int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%lld %lld %lld", &n, &m, &k);
	ll xx1 = 3300, xx2 = 0, yy1 = 3300, yy2 = 0;
	for (int i = 0; i < k; i++)
	{
		ll q, w;
		scanf("%lld %lld", &q, &w);
		xx1 = min(xx1, q);
		xx2 = max(xx2, q);
		yy1 = min(yy1, w);
		yy2 = max(yy2, w);
	}
	fac[0] = 1;
	for (int i = 1; i <= 9000000; i++)
		fac[i] = (fac[i - 1] * i) % mod;
	ll gap = (xx2 - xx1 + 1)*(yy2 - yy1 + 1);
	gap -= k;
	ll dap = fac[gap];
	ll xz = xx2 - xx1 + 1;
	ll yz = yy2 - yy1 + 1;
	dap *= func(xz, yz);
	dap %= mod;
	dap *= comb(n - xz, xx1 - 1);
	dap %= mod;
	dap *= comb(m - yz, yy1 - 1);
	dap %= mod;
	printf("%lld\n", dap);
}

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &q, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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