시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 4 | 4 | 4 | 100.000% |
В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.
Экспериментальная установка содержит квадратную платформу размером 109 × 109, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.
Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (xi, yi).
В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.
Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.
Первая строка входного файла содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000) — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента
Последующие n строк содержат по два целых числа xi, yi (1 ≤ xi, yi ≤ 109) — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.
Требуется вывести одно целое число: максимальную площадь искомого участка
번호 | 배점 | 제한 |
---|---|---|
1 | 18 | 1 ≤ n ≤ 20, 1 ≤ k ≤ n |
2 | 25 | 1 ≤ n ≤ 300, 1 ≤ k ≤ n |
3 | 20 | 1 ≤ n ≤ 3 000, 1 ≤ k ≤ n |
4 | 17 | 2 ≤ n ≤ 200 000, k = 2 |
5 | 20 | 1 ≤ n ≤ 200 000, 1 ≤ k ≤ n |
5 3 3 5 2 2 2 5 4 4 5 3
9
На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.
Рис 1. Силовые поля в примере описания входных данных.
Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2017 7번