1246: Новий рюкзак - ІІ етап, 2017

Перегляд у форматі PDF

Надіслати розв'язок

Бали: 17
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Багатьом вiдома класична задача про рюкзак. У цiй задачi ми маємо \(N\) предметiв iз об'ємом \(C_i\) та вартiстю \(V_i\) i нам треба упакувати у рюкзак предмети на максимальну вартiсть i при цьому не перевищити об'єм рюкзака. На жаль наш рюкзак порвався i треба купити новий. Але новий рюкзак ми хочемо мати такого розмiру, щоб предмети, якi ми туди впакуємо, мали би максимальну сумарну вартiсть. Знайдiть мiнiмальний об'єм рюкзака, що задовольняє описанi вимоги.

Формат вхiдних даних

Перший рядок вхiдного потоку мiстить цiле число \(N\) , де \(1 ⩽ N ⩽ 10^5\) .

Наступнi \(N\) рядкiв мiстять по два цiлих числа - об'єм предмета та його вартiсть: \(C_i\) , \(V_i\) , де \(0 ⩽ C_i ⩽ 10^5\) , - \(10^9 ⩽ V_i ⩽ 10^9 \)

Формат вихiдних даних

У вихiдний потiк вивести мiнiмальний об'єм рюкзака, який помiстить предмети на максимальну суму

Приклад вхідних даних

2
1 0
9 2

Приклад вихідних даних

9

Приклад вхідних даних

1
1 -9000

Приклад вихідних даних

0

Коментарі

Ще немає коментарів.