Ba lô phân số
Points
16
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Một tên trộm đột nhập vào kho báu có $N$ loại vật phẩm. Vật phẩm thứ $i$ có tổng khối lượng $w_i$ và tổng giá trị $v_i$. Chiếc ba lô của tên trộm chỉ chứa được tối đa khối lượng $W$. Khác với bài toán ba lô thông thường, tên trộm có thể lấy một phần bất kỳ (phân số) của một vật phẩm với giá trị tỉ lệ thuận theo khối lượng lấy được. Hãy tìm tổng giá trị lớn nhất mà tên trộm có thể mang đi.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $W$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i$ và $v_i$.
Dữ liệu ra
Một số thực duy nhất là tổng giá trị lớn nhất có thể, làm tròn đến đúng 2 chữ số thập phân.
Ví dụ
| Input | Output |
|---|---|
| 3 50\n10 60\n20 100\n30 120 | 240.00 |
| 1 10\n20 100 | 50.00 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le W \le 10^9$
- $1 \le w_i, v_i \le 10^6$
Community Discussion