Tàu Vũ Trụ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò với kích thước $s_{1}, s_{2}, \dots, s_{N}$ và $N$ chuồng với kích thước $t_{1}, t_{2}, \dots, t_{N}$ . Con bò $i$ có thể vào chuồng $j$ nếu $s_{i} \leq t_{j}$ . Mỗi chuồng chứa tối đa một con bò.

Một ghép cặp tối đại (maximal matching) là một tập hợp các cặp (bò, chuồng) thoả mãn:

Mỗi con bò và mỗi chuồng xuất hiện trong tối đa một cặp.
Mỗi cặp (bò $i$ , chuồng $j$ ) phải có $s_{i} \leq t_{j}$ .
Mọi con bò chưa được ghép đều không vừa bất kỳ chuồng trống nào (tức là không tồn tại chuồng $j$ trống nào có $s_{i} \leq t_{j}$ ).

Đếm số ghép cặp tối đại khác nhau modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
Dòng thứ hai chứa $N$ số nguyên $s_{1}, s_{2}, \dots, s_{N}$ — kích thước các con bò.
Dòng thứ ba chứa $N$ số nguyên $t_{1}, t_{2}, \dots, t_{N}$ — kích thước các chuồng.

Dữ liệu ra

In ra một số nguyên duy nhất — số ghép cặp tối đại modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 3000$
$1 \leq s_{i}, t_{j} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 1 2 3 4 1 2 2 3	9	Có 9 ghép cặp tối đại. Ví dụ, có thể ghép bò kích thước 1 vào chuồng 1, bò kích thước 2 vào một trong hai chuồng kích thước 2, và bò kích thước 3 vào chuồng kích thước 3; bò kích thước 4 không vào được chuồng nào nên không ghép.
8 3 2 1 4 2 1 2 3 4 3 2 4 3 1 3 1	12072	Kết quả là 12072.

Ghi chú

Hai ghép cặp được coi là khác nhau nếu tồn tại ít nhất một cặp (bò, chuồng) thuộc ghép cặp này mà không thuộc ghép cặp kia.

Bình luận

Không có bình luận tại thời điểm này.