oj.uz

Submission #527537

# Submission time Handle Problem Language Result Execution time Memory
527537 2022-02-17T15:15:13 Z rainboy 마스코트 (JOI13_mascots) C
40 / 100
 2 ms 2384 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 208 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 1 ms 424 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 0 ms 208 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -