Назад
 Начало |
 Соревнования |
| 2009 |
Подразделы
| Результаты областной олимпиады |
Другие разделы
| Задачи заочного тура личного первенства |
| Задачи заочного тура олимпиады по информатике |
| Задачи командного чемпионата |
| Задачи очного тура личного первенства |
Дата и время
19/12/2024 20:01:36
Областная олимпиада школьников по информатике
1. Черно-белая графика 2. Газон 3. Трамвай 4. Треугольники 5. Клавиатура 6. Неправильное сложение 7. Числа 8. Перестановки
3. Трамвай
МоделированиеПоразрядная сортировка и сортировка подсчетом
Дерево отрезков, декартово дерево, √-декомпозиция
Олимпиадные задачи на русском языке
| 27/01/2009 | Областная олимпиада школьников по информатике. I тур. (3) |
| 25/03/2013 | Занятие 21 (G) |
| 03/07/2017 | Лето 2017 - 5 (D) |
Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
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/
