Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2473. Линия города
Быстрая сортировкаОлимпиадные задачи на русском языке
| 01/11/2019 | Муниципальный этап 9 класс (3) |
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Озимандии не нравится вид на Манхэттен, и он решил очистить город от существующих зданий
и построить новые небоскрёбы так, чтобы "линии города" (skyline) при взгляде с юга и востока
имели заданную форму.
Напишите программу, которая определяет минимальное количество зданий для получения
заданных "линий города" с юга и востока.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) – ширина вида с юга в зданиях,
следующая строка содержит `N` целых положительных чисел – высоты зданий на "линии города" при взгляде с юга.
Третья строка ввода содержит одно целое число `M` (`1\ ≤\ M\ ≤\ 10^5`) – ширина вида с востока в зданиях,
следующая строка содержит `M` целых положительных чисел – высоты зданий на "линии города" при взгляде с востока.
Вывести одно целое число – минимальное количество зданий. Если получить заданные "линии города"
невозможно, то вывести сообщение "NO".
Пример ввода 1
3 1 6 4 4 6 3 1 2
Пример вывода 1
5
Пример ввода 2
2 1 1 2 5 5
Пример вывода 2
NO
| 6 | 4 | |
| 3 | ||
| 1 | ||
| 2 |
Система оценки и описание подзадач
Подзадача 1 (40 баллов)
`1\ ≤\ N,\ M\ ≤\ 100`, высоты зданий от 1 до 1000
В этой подзадаче 8 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 2 (40 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^5`
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (20 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^9`.
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
