JOI 2018 - Art Exhibition - LQDOJ: Le Quy Don Online Judge

JOI 2018 - Art Exhibition

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một triển lãm mỹ thuật sẽ được tổ chức tại nước JOI, trưng bày các tác phẩm từ khắp cả nước.

Có \(N\) tác phẩm ứng cử cho triển lãm, đánh số từ \(1\) đến \(N\). Mỗi tác phẩm có hai đại lượng nguyên là kích thước và giá trị. Tác phẩm thứ \(i\) có kích thước \(A_i\) và giá trị \(B_i\).

Ban tổ chức sẽ chọn ít nhất một tác phẩm để trưng bày. Hội trường đủ rộng để trưng bày cả \(N\) tác phẩm. Tuy nhiên, theo quan niệm thẩm mỹ của người dân JOI, chênh lệch kích thước giữa các tác phẩm được chọn không nên quá lớn. Mặt khác, ban tổ chức muốn trưng bày nhiều tác phẩm có giá trị cao. Vì vậy, việc lựa chọn tuân theo tiêu chí sau:

Gọi \(A_{\max}\) và \(A_{\min}\) lần lượt là kích thước lớn nhất và nhỏ nhất trong các tác phẩm được chọn; gọi \(S\) là tổng giá trị của chúng.
Chọn các tác phẩm sao cho \(S-(A_{\max}-A_{\min})\) lớn nhất.

Cho số tác phẩm ứng cử, kích thước và giá trị của từng tác phẩm, hãy tính giá trị lớn nhất của biểu thức trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

Dòng đầu chứa số nguyên \(N\), là số tác phẩm ứng cử.
Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_i,B_i\), cách nhau bởi dấu cách, lần lượt là kích thước và giá trị của tác phẩm thứ \(i\).

Dữ liệu ra

Ghi một dòng chứa giá trị lớn nhất của \(S-(A_{\max}-A_{\min})\).

Ràng buộc

\(2\le N\le500\,000\).
\(1\le A_i\le10^{15}\) với \(1\le i\le N\).
\(1\le B_i\le10^9\) với \(1\le i\le N\).

Phân nhóm

(10 điểm) \(N\le16\).
(20 điểm) \(N\le300\).
(20 điểm) \(N\le5000\).
(50 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Có ba tác phẩm: tác phẩm \(1\) có kích thước \(2\), giá trị \(3\); tác phẩm \(2\) có kích thước \(11\), giá trị \(2\); tác phẩm \(3\) có kích thước \(4\), giá trị \(5\).

Chọn tác phẩm \(1\) và \(3\) để trưng bày:

Tác phẩm \(3\) có kích thước lớn nhất trong các tác phẩm được chọn, nên \(A_{\max}=4\).
Tác phẩm \(1\) có kích thước nhỏ nhất, nên \(A_{\min}=2\).
Tổng giá trị là \(S=3+5=8\).

Do đó \(S-(A_{\max}-A_{\min})=8-(4-2)=6\). Không thể đạt giá trị từ \(7\) trở lên, nên đáp án là \(6\).

Ví dụ 2

Input

Output

Ví dụ 3

Input

15
1543361732 260774320
2089759661 257198921
1555665663 389548466
4133306295 296394520
2596448427 301103944
1701413087 274491541
2347488426 912791996
2133012079 444074242
2659886224 656957044
1345396764 259870638
2671164286 233246973
2791812672 585862344
2996614635 91065315
971304780 488995617
1523452673 988137562

Output

4232545716

Nguồn

JOI 2017/2018, vòng chung kết, bài Art Exhibition. Đề do Japanese Committee for the International Olympiad in Informatics công bố. Đề gốc tiếng Anh. Bản dịch tiếng Việt theo CC BY-SA 4.0.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2017/2018 - Vòng chung kết (2 Tháng 1., 2018)