images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 19:49:55

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1195. Трамвай

Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

С окраины в центр города каждое утро по одному маршруту едут в трамвае `N` человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до `P`.
Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого `i`-го пассажира он оценил две величины – `a_i` и `b_i`. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется `a_i`, если же он стоит, то прибавляется `b_i`.
Всего в трамвае `M` сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них `a_i\ <\ b_i`).
Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого `i`-го пассажира известны величины `a_i` и `b_i`, а также номера остановок, на которых он садится и выходит из трамвая.
Формат входных данных
Первая строка входного файла содержит разделенные пробелом три целых числа `N`, `M` и `P` – число пассажиров, число сидячих мест и число остановок на маршруте соответственно (`1\ ≤\ N,\ M\ ≤\ 100\ 000`; `2\ ≤\ P\ ≤\ 100\ 000`).
Каждая из следующих `N` строк содержит информацию об очередном пассажире в виде четырех целых чисел `a_i`, `b_i`, `c_i`, `d_i`, где первые два числа определяют вклад в значение суммарного удовлетворения, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (`-10^6\ ≤\ a_i,\ b_i\ ≤\ 10^6`; `1\ ≤\ c_i\ <\ d_i\ ≤\ P`).
Формат выходных данных
В выходной файл необходимо вывести одно целое число – максимальное значение суммарного удовлетворения, которого могут добиться пассажиры.
Пример входных и выходных данных

input.txt

4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4

output.txt

28
Комментарий к примеру
Максимальное суммарное удовлетворение достигается следующим образом:
  • На первой остановке входят и садятся второй и третий пассажиры;
  • На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
  • На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
  • На четвертой остановке выходят первый и третий пассажиры.

Источник: региональный этап Всероссийской олимпиады по информатике 2008/2009, http://neerc.ifmo.ru/school/
loading