시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 4 | 4 | 4 | 100.000% |
Одна телекоммуникационная компания планирует в скором будущем выпустить на рынок сразу два инновационных смартфона. Эти смартфоны будут называться <<иннофон>> и <<иннофон плюс>>. Устройства уже полностью готовы к производству, и последняя задача, которую необходимо решить руководству компании, --- выбрать оптимальную цену для каждого из смартфонов.
Аналитики компании провели исследование, в результате которого построили следующую модель. Всего есть $n$ потенциальных покупателей инновационных смартфонов. Для принятия решения $i$-й покупатель использует следующий алгоритм, характеризующийся двумя числами $a_i$ и $b_i$ ($a_i \geq b_i$):
Руководство компании хочет установить цены на <<иннофон>> и <<иннофон плюс>> таким образом, чтобы обе цены были целым числом, цена <<иннофона>> была не больше цены <<иннофона плюс>>, и при этом суммарная стоимость проданных смартфонов была максимальна.
Требуется написать программу, которая находит максимально возможную суммарную стоимость проданных смартфонов.
В первой строке содержится целое число $n$ ($1 \leq n \leq 150\,000$) --- число потенциальных покупателей.
В следующих $n$ строках содержатся по два целых числа $a_i$, $b_i$ ($0 \leq b_i \leq a_i \leq 10^9$) --- характеристики алгоритма выбора телефона покупателем с номером $i$.
Выведите одно целое число --- максимальную возможную суммарную стоимость проданных смартфонов.
번호 | 배점 | 제한 |
---|---|---|
1 | 9 | $n \le 100$, $b_i \le a_i \le 100$ |
2 | 10 | $n \le 300$ |
3 | 16 | $n \le 3000$ |
4 | 11 | $n \le 10^5$, $b_i = 0$ |
5 | 16 | $n \le 10^5$, $a_i = b_i$ |
6 | 7 | $n \le 50\,000$ |
7 | 7 | $n \le 75\,000$ |
8 | 8 | $n \le 100\,000$ |
9 | 8 | $n \le 125\,000$ |
10 | 8 | $n \le 150\,000$ |
5 80 20 60 50 40 40 15 10 70 30
220
1 50 0
50
В первом примере для достижения максимальной суммы следует назначить цены на <<иннофон>> и <<иннофон плюс>> равными 40 и 70 соответственно. Тогда первый и пятый покупатель купят <<иннофон плюс>>, второй и третий покупатель купят <<иннофон>>, четвертый покупатель не купит ничего. Суммарная стоимость проданных смартфонов будет $70+40+40+0+70=220$.
Во втором примере нужно сделать цену <<иннофона плюс>> равной 50. Цена на <<иннофон>> при этом не важна.