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


Відправити розв'язок


Бали:6
Time limit:0.5s
Python2.0s
Memory limit:64M
Python125M
Author:

Problem type

Багатьом вiдома класична задача про рюкзак. У цiй задачi ми маємо N предметiв iз об'ємом Ci та варт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сть: Ci , V i , де 0 ⩽ Ci ⩽ 10^5 , - 10^9 ⩽ V i ⩽ 10^9

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

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

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

2
1 0
9 2

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

9

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

1
1 -9000

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

0

Коментарі


  • 0
    Aradam
     прокоментував о Січ. 5, 2018 редагувати 2

    1) Підвищить час для Python.

    2) Виправіть Наступнi N рядкiв мiстять по два цiлих числа - вартiсть предмета та його об'єм (порядок)


    • 0
      zvit
       прокоментував о Січ. 11, 2018
      1. збільшив

      2. там все вірно, об'єм не може бути від'ємним