Thiết kế tuyến đường

Điểm: 1,00 (OI)

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

Python 3 5.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$ địa điểm ở bờ trái và $M$ địa điểm ở bờ phải của một con sông. Địa điểm $i$ bờ trái có giá trị $A_{i}$ ( $1 \leq i \leq N$ ), địa điểm $j$ bờ phải có giá trị $B_{j}$ ( $1 \leq j \leq M$ ). Có $R$ tuyến đường nối các địa điểm bờ trái với bờ phải (không có tuyến nối hai địa điểm cùng bờ).

Một hành trình là một dãy các địa điểm liên kết qua các tuyến đường. Hành trình hợp lệ khi không có hai tuyến đường nào trong hành trình giao nhau. Tuyến $(u_{1} \leftrightarrow v_{1})$ và $(u_{2} \leftrightarrow v_{2})$ giao nhau nếu $u_{1} < u_{2}$ và $v_{1} > v_{2}$ (hoặc ngược lại).

Tìm hành trình hợp lệ sao cho tổng giá trị các địa điểm trong hành trình là lớn nhất.

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $M$ , $R$
Dòng $i + 1$ (với $1 \leq i \leq N$ ): Giá trị $A_{i}$
Dòng $N + j + 1$ (với $1 \leq j \leq M$ ): Giá trị $B_{j}$
Dòng $N + M + k + 1$ (với $1 \leq k \leq R$ ): Hai số nguyên $u_{k}$ và $v_{k}$

Dữ liệu ra

Một số nguyên duy nhất: tổng giá trị lớn nhất

Ràng buộc

$1 \leq N, M \leq 40000$
$0 \leq R \leq 100000$
$0 \leq A_{i}, B_{j} \leq 40000$

Ví dụ

Input	Output	Giải thích
3 2 4 1 1 5 2 2 1 1 2 1 3 1 2 2	8	Hành trình: bờ trái 3 (giá trị 5) → bờ phải 1 (giá trị 2) → bờ trái 2 (giá trị 1) = 8.

Bình luận

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