trang chủ / bài tập / opbying

Bán hàng tối ưu

Đề bài

Mô tả

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 cit là số tiền mà cô sẽ nhận được nếu bán món đồ i (1≤i≤n) ở ngày t (1≤t≤m) hoặc cit=−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≤100);
  • Tiếp theo là n dòng, dòng thứ i (1≤i≤n) chứa m số nguyên ci1,ci2,...,cim (−1≤cit≤100);
  • Tiếp theo là k dòng, mỗi dòng chứa hai số nguyên dương u,v (1≤u,v≤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≤100
  • −1≤cit≤100
  • Subtask 1 (25 điểm): n≤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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0