Balo phân số
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ món đồ, món thứ $i$ có trọng lượng $W_i$ và giá trị $V_i$. Bạn có một chiếc balo có sức chứa tối đa $C$. Bạn có thể lấy toàn bộ hoặc một phần bất kỳ của mỗi món đồ (nếu lấy phần tỉ lệ $p \in [0, 1]$ thì tốn $p \cdot W_i$ sức chứa và thu được $p \cdot V_i$ giá trị). Hãy tính tổng giá trị lớn nhất có thể mang theo.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N$ và $C$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $W_i$ và $V_i$.
Dữ liệu ra
In ra tổng giá trị lớn nhất, làm tròn chính xác đến $2$ chữ số thập phân.
Ví dụ
| Input | Output |
|---|---|
| 3 50 10 60 20 100 30 120 |
240.00 |
Giới hạn
- $1 \le N \le 10^5$.
- $1 \le C, W_i, V_i \le 10^9$.
Community Discussion