Tối đa hóa vốn đầu tư

Buổi 12 — Greedy Algorithm greedy sorting
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Một công ty khởi nghiệp bắt đầu với số vốn ban đầu là $W$. Có $N$ dự án đầu tư khả thi; dự án thứ $i$ yêu cầu số vốn tối thiểu $c_i$ để có thể khởi chạy và sau khi hoàn thành sẽ mang lại lợi nhuận ròng $p_i$ (tức là vốn của công ty tăng thêm $p_i$, không mất đi vốn $c_i$). Công ty chỉ được chọn thực hiện tuần tự tối đa $K$ dự án khác nhau. Hãy tìm số vốn lớn nhất công ty có thể đạt được sau khi thực hiện tối đa $K$ dự án.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, K, W$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $c_i$ và $p_i$.
Dữ liệu ra

Một số nguyên duy nhất là số vốn lớn nhất có thể đạt được.

Ví dụ
Input Output
3 2 0\n0 1\n1 2\n1 3 4
3 3 0\n0 1\n1 2\n2 3 6
Giới hạn
  • $1 \le N, K \le 10^5$
  • $0 \le W, c_i, p_i \le 10^9$
Draft saved