Ochko'z algoritmlar
Greedy-04
Greedy-05
Geometriya-01
~/algor $ cat masalalar/ochkoz-kasrli-yukxalta
Greedy-05
Bo'linadigan yuklar
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
2000 ms
128 MB
66%
Xaltaga ko'pi bilan $W$ kg yuk sig'adi. $n$ ta yuk bor: $i$-yukning qiymati $v_{i}$, og'irligi $w_{i}$ kg. Yuklarni bo'lish mumkin: $i$-yukning $x$ kg qismi ($0 \le x \le w_{i}$) olinsa, uning qiymati
$$v_{i} * \frac{x}{w_{i}}$$
bo'ladi. Xaltadagi yuklarning eng katta umumiy qiymatini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita natural son: $n$ va $W$. Keyingi $n$ ta qatorning har birida ikkita natural son: $v_{i}$ va $w_{i}$.
Chiquvchi ma'lumotlar
Bitta haqiqiy son — eng katta umumiy qiymat, nuqtadan keyin aynan $3$ ta raqam bilan (masalan, 240.000).
Izoh
$1 \le n \le 10^{5}$
$1 \le v_{i}, w_{i} \le 10^{6}$
$1 \le W \le 10^{11}$
Misollar
Kirish #1
3 50 60 10 100 20 120 30
Chiqish #1
240.000
Kirish #2
2 5 10 10 3 1
Chiqish #2
7.000