Công việc và Hạn chót

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Bạn cần hoàn thành $n$ công việc theo một thứ tự nào đó. Công việc thứ $i$ có thời gian thực hiện $a_{i}$ và hạn chót $d_{i}$ . Phần thưởng nhận được khi hoàn thành công việc $i$ bằng $d_{i} - f_{i}$ , trong đó $f_{i}$ là thời điểm bạn hoàn thành công việc đó. Hãy tìm thứ tự thực hiện để tổng phần thưởng là lớn nhất.

Lưu ý: bạn phải hoàn thành tất cả các công việc, và phần thưởng có thể âm.

Dữ liệu vào

Dòng đầu: số nguyên $n$ .
$n$ dòng tiếp theo, dòng thứ $i$ : hai số nguyên $a_{i}$ và $d_{i}$ .

Dữ liệu ra

In một số nguyên — tổng phần thưởng tối đa.

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a_{i}, d_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 6 10 8 15 5 12	2	Thứ tự tối ưu: công việc 3 (a=5, d=12), công việc 1 (a=6, d=10), công việc 2 (a=8, d=15). Phần thưởng: $(12 - 5) + (10 - 11) + (15 - 19) = 7 - 1 - 4 = 2$ .
2 1 1 1 1000000	999998	Thứ tự tối ưu: công việc 1 (a=1, d=1), công việc 2 (a=1, d=1000000). Phần thưởng: $(1 - 1) + (1000000 - 2) = 999998$ .

Bình luận

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