oj.uz

Submission #142742

# Submission time Handle Problem Language Result Execution time Memory
142742 2019-08-10T16:09:34 Z gs18103 마스코트 (JOI13_mascots) C++14
100 / 100
 591 ms 184468 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define fastio ios::sync_with_stdio(false); cin.tie(NULL)
#define INF 2000000000;
#define LINF 1000000000000000000LL
#define mod 1000000007

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

int r, c;
ll dp[3030][3030], fact[9090909], C[3030][3030];

ll f(int x, int y) {
	if(x > r || y > c) return 0;
	if(x == r && y == c) return 1;
	if(dp[x][y] != 0) return dp[x][y];
	dp[x][y] += (fact[x] * f(x, y+1)) % mod;
	dp[x][y] += (fact[y] * f(x+1, y)) % mod;
	dp[x][y] %= mod;
	return dp[x][y];
}

int main() {
	fastio;
	int n, mx = 0, my = 0, mix = 3030, miy = 3030;
	C[0][0] = 1;
	for(int i = 1; i <= 3000; i++) {
		C[i][0] = 1;
		for(int j = 1; j <= i; j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
		}
	}

	cin >> r >> c >> n;
	fact[0] = 1;
	for(int i = 1; i <= r * c; i++) {
		fact[i] = (fact[i-1] * i) % mod;
	}
	for(int i = 1, x, y; i <= n; i++) {
		cin >> x >> y;
		mix = min(mix, x);
		mx = max(mx, x);
		miy = min(miy, y);
		my = max(my, y);
	}
	ll ans = (f(mx-mix+1, my-miy+1) * fact[(mx-mix+1)*(my-miy+1)-n]) % mod;
	ans = (ans * C[r-(mx-mix+1)][mix-1]) % mod;
	ans = (ans * C[c-(my-miy+1)][miy-1]) % mod;
	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 46712 KB Output is correct
2 Correct 48 ms 46744 KB Output is correct
3 Correct 46 ms 46684 KB Output is correct
4 Correct 45 ms 46840 KB Output is correct
5 Correct 45 ms 46840 KB Output is correct
6 Correct 45 ms 46712 KB Output is correct
7 Correct 45 ms 46712 KB Output is correct
8 Correct 51 ms 46900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 46840 KB Output is correct
2 Correct 48 ms 46816 KB Output is correct
3 Correct 48 ms 46840 KB Output is correct
4 Correct 46 ms 46840 KB Output is correct
5 Correct 53 ms 46816 KB Output is correct
6 Correct 45 ms 46688 KB Output is correct
7 Correct 46 ms 46712 KB Output is correct
8 Correct 45 ms 46712 KB Output is correct
9 Correct 46 ms 47116 KB Output is correct
10 Correct 46 ms 46840 KB Output is correct
11 Correct 45 ms 46740 KB Output is correct
12 Correct 45 ms 46712 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 47128 KB Output is correct
2 Correct 48 ms 47992 KB Output is correct
3 Correct 51 ms 48944 KB Output is correct
4 Correct 103 ms 62072 KB Output is correct
5 Correct 92 ms 61044 KB Output is correct
6 Correct 96 ms 60572 KB Output is correct
7 Correct 71 ms 61816 KB Output is correct
8 Correct 95 ms 78084 KB Output is correct
9 Correct 165 ms 118008 KB Output is correct
10 Correct 589 ms 173020 KB Output is correct
11 Correct 373 ms 150068 KB Output is correct
12 Correct 155 ms 109676 KB Output is correct
13 Correct 58 ms 53840 KB Output is correct
14 Correct 154 ms 117220 KB Output is correct
15 Correct 572 ms 184468 KB Output is correct
16 Correct 490 ms 144300 KB Output is correct
17 Correct 199 ms 122204 KB Output is correct
18 Correct 591 ms 181852 KB Output is correct