10/04/2025 23:08:22

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

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

Задачи

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

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

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

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

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

Задачи

2438. Купол на Марсе

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

Доктор Манхэттен решил построить город на Марсе из

$K$ домов. Каждый дом должен быть построен по собственному уникальному проекту, который выбирается среди

$N$ проектов. Все проекты предусматривают строительство домов прямоугольной формы, но размеры домов различны – по

$i$ -му проекту дом имеет ширину

$W_i$ и высоту

$H_i$ . Дома строятся на одной линии, рядом друг с другом. После строительства город закрывается куполом, который имеет прямоугольную форму, и заполняется воздухом. Так как доставка воздуха с Земли слишком сложна, то нужно минимизировать размер купола.

Напишите программу, которая выберет

$K$ проектов для домов из

$N$ проектов таким образом, чтобы необходимый объем воздуха для заполнения купола (произведение ширины купола на его высоту) был минимальным.

Для первого примера минимальный объем (20 единиц) получается при выборе следующих 3 домов:

Формат ввода

Первая строка ввода содержит два целых числа – количество проектов

$N$ и количество домов

$K$ (

$1\ ≤\ K\ ≤\ N\ ≤\ 1\ 000\ 000$ ). Следующие

$N$ строк содержат по два целых числа – ширина

$W_i$ и высота

$H_i$ дома по

$i$ -му проекту (

$1\ ≤\ W_i,\ H_i\ ≤\ 1\ 000\ 000$ ). Все пары

$(W_i,\ H_i)$ различны.

Формат вывода

Вывести одно целое число – минимальный объем воздуха для заполнения купола.

Пример ввода 1

Пример вывода 1

Пример ввода 2

Пример вывода 2

Пример ввода 3

Пример вывода 3

Источник: COCI 2018/2019 contest #4