Submission #527537

#	Time	Username	Problem	Language	Result	Execution time	Memory
527537		rainboy	마스코트 (JOI13_mascots)	C11	40 / 100	2 ms	2384 KiB

mascots

#include <stdio.h>

#define N	50
#define M	50
#define MD	1000000007

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ff[N * M + 1];

void init() {
	int i;

	ff[0] = 1;
	for (i = 1; i <= N * M; i++)
		ff[i] = (long long) ff[i - 1] * i % MD;
}

int main() {
	static int dp[N][N][M][M];
	int n, m, k, h, i, il, il_, ir, ir_, j, jl, jl_, jr, jr_;

	init();
	scanf("%d%d%d", &n, &m, &k);
	il_ = n, ir_ = -1, jl_ = m, jr_ = -1;
	for (h = 0; h < k; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		il_ = min(il_, i), ir_ = max(ir_, i), jl_ = min(jl_, j), jr_ = max(jr_, j);
	}
	dp[il_][ir_][jl_][jr_] = ff[(ir_ - il_ + 1) * (jr_ - jl_ + 1) - k];
	for (il = il_; il >= 0; il--)
		for (ir = ir_; ir < n; ir++)
			for (jl = jl_; jl >= 0; jl--)
				for (jr = jr_; jr < m; jr++) {
					if (il < il_)
						dp[il][ir][jl][jr] = (dp[il][ir][jl][jr] + (long long) dp[il + 1][ir][jl][jr] * ff[jr - jl + 1]) % MD;
					if (ir > ir_)
						dp[il][ir][jl][jr] = (dp[il][ir][jl][jr] + (long long) dp[il][ir - 1][jl][jr] * ff[jr - jl + 1]) % MD;
					if (jl < jl_)
						dp[il][ir][jl][jr] = (dp[il][ir][jl][jr] + (long long) dp[il][ir][jl + 1][jr] * ff[ir - il + 1]) % MD;
					if (jr > jr_)
						dp[il][ir][jl][jr] = (dp[il][ir][jl][jr] + (long long) dp[il][ir][jl][jr - 1] * ff[ir - il + 1]) % MD;
				}
	printf("%d\n", dp[0][n - 1][0][m - 1]);
	return 0;
}

Compilation message (stderr)

mascots.c: In function 'main':
mascots.c:25:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d%d%d", &n, &m, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
mascots.c:28:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

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