302696: CF524B. Фото на память - 2 (round version)

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Фото на память - 2 (round version)

题意翻译

### 题目描述 许多年过去了,$ n $个朋友在派对相聚。自从上一次聚会,科技已经发生了巨大的进步,所以相机已经有了自拍功能,所以不需要其中的一个朋友站在相机前而因此不能参与合照。 拍照的过程可以按如下方式简化。在照片中,每个朋友占据一块长方形的像素块:站在第$ i $个位置的人占据着宽度为$ w_i $,高度为$ h_i $的像素块。当然,在照相时,每个人都可以躺下来,此时他会占据一个宽度为$ h_i $,高度为$ w_i $的像素块。 整个照片将会有$ W \times H $的大小,$ W $是照片的总宽度,$ H $是照片的总高度。朋友们想确定整张照片的最小的大小。请帮助他们。 ### 输入格式 第一行输入一个整数$ n $( $ 1<=n<=1000 $ ),代表朋友的数量。 接下来的的$ n $行每行两个整数$ w_i $和$ h_i $( $ 1<=w_{i},h_{i}<=1000 $ ),代表第$ i $个朋友要占据的长方形的长和宽 ### 输出格式 输出一个整数为能将所有朋友包括在内的最小照片的大小。 Translated by zhouyonglong

题目背景

Photo for memory - 2 (round version) 照片记忆 - 2 (圆形版本)

题目描述

Прошло много лет, и на вечеринке снова встретились $ n $ друзей. С момента последней встречи техника шагнула далеко вперёд, появились фотоаппараты с автоспуском, и теперь не требуется, чтобы один из друзей стоял с фотоаппаратом, и, тем самым, оказывался не запечатлённым на снимке. Упрощенно процесс фотографирования можно описать следующим образом. На фотографии каждый из друзей занимает прямоугольник из пикселей: в стоячем положении $ i $ -й из них занимает прямоугольник ширины $ w_{i} $ пикселей и высоты $ h_{i} $ пикселей. Но также, при фотографировании каждый человек может лечь, и тогда он будет занимать прямоугольник ширины $ h_{i} $ пикселей и высоты $ w_{i} $ пикселей. Общая фотография будет иметь размеры $ W×H $ , где $ W $ — суммарная ширина всех прямоугольников-людей, а $ H $ — максимальная из высот. Друзья хотят определить, какую минимальную площадь может иметь общая фотография. Помогите им в этом.

输入输出格式

输入格式


В первой строке следует целое число $ n $ ( $ 1<=n<=1000 $ ) — количество друзей. В последующих $ n $ строках следуют по два целых числа $ w_{i},h_{i} $ ( $ 1<=w_{i},h_{i}<=1000 $ ), обозначающие размеры прямоугольника, соответствующего $ i $ -му из друзей.

输出格式


Выведите единственное целое число, равное минимальной возможной площади фотографии, вмещающей всех друзей.

输入输出样例

输入样例 #1

3
10 1
20 2
30 3

输出样例 #1

180

输入样例 #2

3
3 1
2 2
4 3

输出样例 #2

21

输入样例 #3

1
5 10

输出样例 #3

50

Input

题意翻译

### 题目描述 许多年过去了,$ n $个朋友在派对相聚。自从上一次聚会,科技已经发生了巨大的进步,所以相机已经有了自拍功能,所以不需要其中的一个朋友站在相机前而因此不能参与合照。 拍照的过程可以按如下方式简化。在照片中,每个朋友占据一块长方形的像素块:站在第$ i $个位置的人占据着宽度为$ w_i $,高度为$ h_i $的像素块。当然,在照相时,每个人都可以躺下来,此时他会占据一个宽度为$ h_i $,高度为$ w_i $的像素块。 整个照片将会有$ W \times H $的大小,$ W $是照片的总宽度,$ H $是照片的总高度。朋友们想确定整张照片的最小的大小。请帮助他们。 ### 输入格式 第一行输入一个整数$ n $( $ 1<=n<=1000 $ ),代表朋友的数量。 接下来的的$ n $行每行两个整数$ w_i $和$ h_i $( $ 1<=w_{i},h_{i}<=1000 $ ),代表第$ i $个朋友要占据的长方形的长和宽 ### 输出格式 输出一个整数为能将所有朋友包括在内的最小照片的大小。 Translated by zhouyonglong

加入题单

上一题 下一题 算法标签: