Submission #26410

#	Time	Username	Problem	Language	Result	Execution time	Memory
26410		zscoder	마스코트 (JOI13_mascots)	C++14	100 / 100	336 ms	230460 KiB

mascots

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD = 1e9 + 7;

ll fact[10000001];
ll rl, rr, cl, cr;
ll choose[3100][3100];
ll dp[3100][3100];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll r, c; cin>>r>>c;
	ll n; cin>>n;
	ll rmin, rmax, cmin, cmax;
	rmin = r+1; rmax = 0; cmin = c+1; cmax = 0;
	for(ll i = 0; i < n; i++)
	{
		ll x, y;
		cin >> x >> y;
		rmin = min(x, rmin);
		rmax = max(x, rmax);
		cmin = min(y, cmin);
		cmax = max(y, cmax);
	}
	rl = rmin; rr = rmax; cl = cmin; cr = cmax;
	fact[0] = 1;
	for(ll i = 1; i <= 10000000; i++)
	{
		fact[i] = (fact[i - 1]*i)%MOD;
	}
	for(ll i = 0; i < 3100; i++)
	{
		choose[i][0] = 1;
	}
	for(ll j = 1; j < 3100; j++)
	{
		for(ll i = 1; i < 3100; i++)
		{
			if(i < j) choose[i][j] = 0;
			else if(i == j) choose[i][j] = 1;
			else
			{
				choose[i][j] = (ll(choose[i - 1][j]) + ll(choose[i - 1][j - 1]))%MOD;
			}
		}
	}
	ll tmp = (rmax - rmin + 1)*(cmax - cmin + 1);
	tmp -= n;
	tmp = fact[tmp];
	
	ll h = rmax - rmin + 1;
	ll w = cmax - cmin + 1;
	
	dp[h][w] = tmp;
	for(ll i = h; i <= r; i++)
	{
		for(ll j = w; j <= c; j++)
		{
			dp[i][j] = (dp[i][j] + (dp[i - 1][j]*fact[j])%MOD + (dp[i][j - 1]*fact[i])%MOD)%MOD;
		}
	}
	ll answer = dp[r][c];
	answer = (answer*ll(choose[rmin-1+r-rmax][rmin-1]))%MOD;
	answer = (answer*ll(choose[cmin-1+c-cmax][cmin-1]))%MOD;
	cout << answer;

	return 0;
}

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