oj.uz

Submission #25977

# Submission time Handle Problem Language Result Execution time Memory
25977 2017-06-25T09:20:29 Z abcdef6199 마스코트 (JOI13_mascots) C++
10 / 100
 3 ms 108192 KB 
#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];
	cout << (LL) ans * mul % P;
	return 0;
}

Compilation message

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

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 108192 KB Output is correct
2 Correct 0 ms 108192 KB Output is correct
3 Correct 0 ms 108192 KB Output is correct
4 Correct 0 ms 108192 KB Output is correct
5 Correct 0 ms 108192 KB Output is correct
6 Correct 0 ms 108192 KB Output is correct
7 Correct 0 ms 108192 KB Output is correct
8 Correct 0 ms 108192 KB Output is correct
9 Incorrect 0 ms 108192 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

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