Submission #212717

#	Time	Username	Problem	Language	Result	Execution time	Memory
212717		patrikpavic2	마스코트 (JOI13_mascots)	C++17	100 / 100	173 ms	37112 KiB

mascots

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 3e3 + 50;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

inline int add(int A,int B){
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int mul(int A,int B){
	return (ll)A * B % MOD;
}

inline int pot(int A,int B){
	int ret = 1, base = A;
	for(;B;B >>= 1){
		if(B&1) ret = mul(ret, base);
		base = mul(base, base);
	}
	return ret;
}

int fak[N], inv[N], dp[N][N];
int n, m, mi_X , mx_X, mi_Y, mx_Y, x, y, q;

void precompute(){
	fak[0] = 1, inv[0] = 1;
	for(int i = 1;i < N;i++){
		fak[i] = mul(fak[i - 1], i);
		inv[i] = pot(fak[i], MOD - 2);
	}
}

inline int choose(int n,int k){
	return mul(fak[n], mul(inv[k], inv[n - k]));
}

void racunaj(){
	for(int i = n;i >= 1;i--){
		for(int j = m;j >= 1;j--){
			dp[i][j] = (i == n && j == m);
			if(i + 1 <= n)
				dp[i][j] = add(dp[i][j], mul(dp[i + 1][j], fak[j]));
			if(j + 1 <= m)
				dp[i][j] = add(dp[i][j], mul(dp[i][j + 1], fak[i]));
		}
	}
}


int main(){
	scanf("%d%d%d", &n, &m, &q);
	precompute(); racunaj();
	scanf("%d%d", &x, &y); 
	mi_X = x, mx_X = x;
	mi_Y = y, mx_Y = y;
	for(int i = 1;i < q;i++){
		scanf("%d%d", &x, &y);
		mi_X = min(x, mi_X);
		mx_X = max(x, mx_X);
		mi_Y = min(y, mi_Y);
		mx_Y = max(y, mx_Y);
	}
	int a = mx_X - mi_X + 1;
	int b = mx_Y - mi_Y + 1;
	int sol = mul(choose(n - a, mi_X - 1), choose(m - b, mi_Y - 1));
	for(int i = 1;i <= a * b - q;i++)
		sol = mul(sol, i);
	printf("%d\n", mul(sol, dp[a][b]));
	return 0;
}

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &x, &y); 
  ~~~~~^~~~~~~~~~~~~~~~
mascots.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

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