trang chủ / đề bài / icpcwf17_d

Tiền từ hư không

Đề bài

Mô tả

Trong bài này, bạn sẽ giải một trong những thử thách sâu sắc nhất của loài người trên khắp thế giới từ thuở khai thiên lập địa: làm thế nào để kiếm thật nhiều tiền.

Bạn là người trung gian trên thị trường widget. Công việc của bạn là mua widget từ các công ty sản xuất widget và bán chúng cho các công ty tiêu thụ widget. Mỗi công ty tiêu thụ có một yêu cầu mở là mua một widget mỗi ngày cho đến một ngày kết thúc nào đó, với một mức giá mà công ty sẵn sàng trả cho mỗi widget. Mặt khác, mỗi công ty sản xuất có một ngày bắt đầu, từ đó công ty có thể giao widget, và một mức giá cho mỗi widget giao đi.

Do luật cạnh tranh công bằng, bạn chỉ được ký hợp đồng với đúng một công ty sản xuất và đúng một công ty tiêu thụ. Bạn sẽ mua widget từ công ty sản xuất, mỗi ngày một chiếc, bắt đầu từ ngày công ty đó có thể bắt đầu giao hàng và kết thúc vào ngày do công ty tiêu thụ quy định. Vào mỗi ngày trong khoảng đó, bạn kiếm được phần chênh lệch giữa giá bán của công ty sản xuất và giá mua của công ty tiêu thụ.

Mục tiêu của bạn là chọn công ty tiêu thụ và công ty sản xuất sao cho lợi nhuận lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên m và n (1≤m,n≤500000), lần lượt là số công ty sản xuất và số công ty tiêu thụ trên thị trường.

Tiếp theo là m dòng, dòng thứ i chứa hai số nguyên pi và di (1≤pi,di≤109): giá (tính bằng đô la) mà công ty sản xuất thứ i bán một widget và ngày mà widget đầu tiên của công ty này sẵn sàng.

Sau đó là n dòng, dòng thứ j chứa hai số nguyên qj và ej (1≤qj,ej≤109): giá (tính bằng đô la) mà công ty tiêu thụ thứ j sẵn sàng trả cho một widget và ngày ngay sau ngày cuối cùng phải giao widget cho công ty này.

Dữ liệu ra

In ra tổng số đô la lớn nhất bạn có thể kiếm được. Nếu không có cách ký hợp đồng nào mang lại lợi nhuận dương, in ra 0.

Ràng buộc

  • 1≤m,n≤500000.
  • 1≤pi,di≤109 với mọi 1≤i≤m.
  • 1≤qj,ej≤109 với mọi 1≤j≤n.

Ví dụ

Input Output Giải thích
2 2
1 3
2 1
3 5
7 2
5 Chọn công ty sản xuất thứ hai (giá 2, từ ngày 1) và công ty tiêu thụ thứ hai (giá 7, ngày kết thúc 2): giao widget vào ngày 1, lãi (2−1)·(7−2)=5.
1 2
10 10
9 11
11 9
0 Công ty tiêu thụ thứ nhất trả giá 9 thấp hơn giá bán 10, công ty tiêu thụ thứ hai kết thúc ở ngày 9 trước ngày bắt đầu 10: không có hợp đồng nào có lãi.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0