Bán hàng tối ưu

Điểm: 7,00 (OI)

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

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

Input: stdin

Output: stdout

Nguồn bài:

23-24 DHBB K11

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Alice có $n$ món đồ cổ và muốn bán tất cả trong $m$ ngày. Cô đã tìm hiểu và biết được $c_{i t}$ là số tiền mà cô sẽ nhận được nếu bán món đồ $i$ ( $1 \leq i \leq n$ ) ở ngày $t$ ( $1 \leq t \leq m$ ) hoặc $c_{i t} = - 1$ nếu không ai muốn mua món đồ $i$ ở ngày $t$ . Một số món đồ phải được bán trước một số món đồ khác, có $k$ ràng buộc như vậy, mỗi ràng buộc có dạng $(u, v)$ và có nghĩa là món đồ $u$ phải được bán trước ít nhất một ngày so với ngày bán món đồ $v$ . Alice muốn lên kế hoạch bán tối ưu để có thể thu được nhiều tiền nhất. Chú ý rằng, mỗi ngày Alice có thể bán nhiều hơn một món đồ miễn là các món đồ liên quan đến ràng buộc bán trước các món đồ này đều đã được bán ở các ngày trước.

Giúp Alice tính số tiền nhiều nhất có thể nhận được khi bán tối ưu tất cả các món đồ.

Dữ liệu vào

Dòng đầu tiên ghi ba số nguyên dương $n, m, k$ ( $n, m, k \leq 100$ );
Tiếp theo là $n$ dòng, dòng thứ $i$ ( $1 \leq i \leq n$ ) chứa $m$ số nguyên $c_{i 1}, c_{i 2}, . . ., c_{i m}$ ( $- 1 \leq c_{i t} \leq 100$ );
Tiếp theo là $k$ dòng, mỗi dòng chứa hai số nguyên dương $u, v$ ( $1 \leq u, v \leq n$ ) cho biết món đồ $u$ phải được bán trước ít nhất một ngày so với ngày bán món đồ $v$ .

Dữ liệu đảm bảo có cách bán hết cả $n$ món đồ.

Dữ liệu ra

Một dòng là số tiền nhiều nhất có thể nhận được khi bán tối ưu tất cả các món đồ.

Ràng buộc

$n, m, k \leq 100$
$- 1 \leq c_{i t} \leq 100$
Subtask 1 (25 điểm): $n \leq 15$
Subtask 2 (35 điểm): Trong $k$ ràng buộc không có hai ràng buộc nào có cùng giá trị $v$
Subtask 3 (40 điểm): Không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
3 2 2 100 -1 100 80 100 90 1 2 1 3	270

Bình luận

giangkoi

đã bình luận lúc 12, Tháng 4, 2025, 8:55

😨😰😱🥶

myduydau_2023

đã bình luận lúc 10, Tháng 4, 2025, 14:00

hi

new_coder

đã bình luận lúc 7, Tháng 12, 2024, 9:36

hi ae