Submission #25978

#	Time	Username	Problem	Language	Result	Execution time	Memory
25978		abcdef6199	마스코트 (JOI13_mascots)	C++98	100 / 100	176 ms	108192 KiB

mascots

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;

const int N = 3000 + 10;
const int P = (int) 1e9 + 7;
int n, m, k;
int C[N][N];
int dp[N][N];
int fac[N * N];

int main() {
	scanf("%d%d", &n, &m);
	int r1 = n + 1, r2 = -1;
	int c1 = m + 1, c2 = -1;
	scanf("%d", &k);
	for (int i = 1; i <= k; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		r1 = min(r1, x); r2 = max(r2, x);
		c1 = min(c1, y); c2 = max(c2, y);
	}

	fac[0] = 1;
	for (int i = 1; i <= n * m; ++i) fac[i] = (LL) fac[i - 1] * i % P;
	for (int i = 0; i <= max(n, m); ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
			if (C[i][j] >= P) C[i][j] -= P;
		}
	}

	int lx = r2 - r1 + 1;
	int ly = c2 - c1 + 1;
	dp[lx][ly] = fac[lx * ly - k];
	for (int i = lx; i <= n; ++i) for (int j = ly; j <= m; ++j) {
		if (i < n) dp[i + 1][j] = (dp[i + 1][j] + (LL) dp[i][j] * fac[j]) % P;
		if (j < m) dp[i][j + 1] = (dp[i][j + 1] + (LL) dp[i][j] * fac[i]) % P;
	}

	int ans = dp[n][m];
	int mul = (LL) C[n - lx][r1 - 1] * C[m - ly][c1 - 1] % P;
	cout << (LL) ans * mul % P;
	return 0;
}

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:15:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
mascots.cpp:18:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
                 ^
mascots.cpp:20:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

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