07/04/2025 04:17:04

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1195. Трамвай

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

С окраины в центр города каждое утро по одному маршруту едут в трамвае

$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

output.txt

Комментарий к примеру

Максимальное суммарное удовлетворение достигается следующим образом:

На первой остановке входят и садятся второй и третий пассажиры;
На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
На четвертой остановке выходят первый и третий пассажиры.

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

27/01/2009	Областная олимпиада школьников по информатике. I тур. (3)
25/03/2013	Занятие 21 (G)
03/07/2017	Лето 2017 - 5 (D)