oj.uz

Submission #212717

# Submission time Handle Problem Language Result Execution time Memory
212717 2020-03-24T07:35:25 Z patrikpavic2 마스코트 (JOI13_mascots) C++17
100 / 100
 173 ms 37112 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 3e3 + 50;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

inline int add(int A,int B){
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int mul(int A,int B){
	return (ll)A * B % MOD;
}

inline int pot(int A,int B){
	int ret = 1, base = A;
	for(;B;B >>= 1){
		if(B&1) ret = mul(ret, base);
		base = mul(base, base);
	}
	return ret;
}

int fak[N], inv[N], dp[N][N];
int n, m, mi_X , mx_X, mi_Y, mx_Y, x, y, q;

void precompute(){
	fak[0] = 1, inv[0] = 1;
	for(int i = 1;i < N;i++){
		fak[i] = mul(fak[i - 1], i);
		inv[i] = pot(fak[i], MOD - 2);
	}
}

inline int choose(int n,int k){
	return mul(fak[n], mul(inv[k], inv[n - k]));
}

void racunaj(){
	for(int i = n;i >= 1;i--){
		for(int j = m;j >= 1;j--){
			dp[i][j] = (i == n && j == m);
			if(i + 1 <= n)
				dp[i][j] = add(dp[i][j], mul(dp[i + 1][j], fak[j]));
			if(j + 1 <= m)
				dp[i][j] = add(dp[i][j], mul(dp[i][j + 1], fak[i]));
		}
	}
}


int main(){
	scanf("%d%d%d", &n, &m, &q);
	precompute(); racunaj();
	scanf("%d%d", &x, &y); 
	mi_X = x, mx_X = x;
	mi_Y = y, mx_Y = y;
	for(int i = 1;i < q;i++){
		scanf("%d%d", &x, &y);
		mi_X = min(x, mi_X);
		mx_X = max(x, mx_X);
		mi_Y = min(y, mi_Y);
		mx_Y = max(y, mx_Y);
	}
	int a = mx_X - mi_X + 1;
	int b = mx_Y - mi_Y + 1;
	int sol = mul(choose(n - a, mi_X - 1), choose(m - b, mi_Y - 1));
	for(int i = 1;i <= a * b - q;i++)
		sol = mul(sol, i);
	printf("%d\n", mul(sol, dp[a][b]));
	return 0;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &x, &y); 
  ~~~~~^~~~~~~~~~~~~~~~
mascots.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 720 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 7 ms 1792 KB Output is correct
3 Correct 7 ms 1920 KB Output is correct
4 Correct 16 ms 6912 KB Output is correct
5 Correct 16 ms 6784 KB Output is correct
6 Correct 41 ms 9088 KB Output is correct
7 Correct 33 ms 12084 KB Output is correct
8 Correct 56 ms 24032 KB Output is correct
9 Correct 159 ms 36728 KB Output is correct
10 Correct 94 ms 33912 KB Output is correct
11 Correct 95 ms 30204 KB Output is correct
12 Correct 173 ms 36768 KB Output is correct
13 Correct 15 ms 6144 KB Output is correct
14 Correct 161 ms 36176 KB Output is correct
15 Correct 128 ms 36856 KB Output is correct
16 Correct 79 ms 26360 KB Output is correct
17 Correct 163 ms 36704 KB Output is correct
18 Correct 132 ms 37112 KB Output is correct