Ну я так понимаю, что можно будет узнать ответ как только этот раунд будет добавлен на сайт. :D

Я делал так. Во-первых, понятно, что можно считать, что в каждой паре x_i < y_i и ничего вращать нельзя. Теперь найдём минимум по x и минимум по y. Они либо в одной корзине, либо в разных. Если в одной — то надо просто выбрать N штук для второй, максимизируя площадь (это делается сортировкой по x, проходом в этом порядке и поддержанием set'а по y). Если в разных — то надо опять же посортить по x, перебрать, какой x пойдёт к минимальному y, тогда получается, что к минимальному x пойдут все x меньше этого + сколько-то с x не меньше этого (из них надо выбирать максимальные y, ясное дело). Это тоже считается проходом с set'ом.

Upd. Правда, оно у меня упало на каком-то хитром тесте, видимо, руки у меня кривые :)

1. Повернем все прямоугольники так, чтобы их вертикальная сторона была не больше, чем горизонтальная.
2. Отсортируем их по неубыванию вертикальной стороны.
3. Понятно, что длина вертикальной стороны сумки определяется длиной вертикальной стороны прямоугольника с наименьшем индексом, который попал в эту сумку. А длина горизонтальной стороны — минимум среди всех горизонтальных сторон.
4. Понятно, что первый прямоугольник попадет в какую-то сумку. Пусть в первую. Теперь переберем i = [2..N + 1] — индекс самого левого прямоугольника во второй сумке.
5. Понятно, что прямоугольники с [2..i-1] попадут в первую сумку. Тогда осталось распределить оптимально оставшиеся прямоуголь с [i + 1..2N]. Так как мы зафиксировали вертикальную сторону, то оставшиеся сумки выгодно распределять так: отсортируем их под горизонтальный стороне, первые сколько-то уйдут в одну сумку, а остальные в другую.
6. Так как мы знаем количество прямоугольником в обоих сумках (i — 1 в первой, 1 во второй), то мы можем перебрать в какую сумку уйдет суффикс, а в какую — префикс оставшихся прямоугольников отсортированых по горизонтальной стороне. Пусть префикс уходит в сумку, в который сейчас находится A прямоугольников. Тогда в длина горизонтальной стороны этой сумки равна длине горизонтальной стороны первого оставшегося прямоугольника, а у другой сумке — это длина горизонтальной стороны (n — A + 1)-го оставшегося прямоугольника. Это можно вычислять за логарифм, если применить сжатие координат по горизотальным сторонам и хранить оставшиеся прямоугольники в дереве отрезков.

Пускай X[i] <= Y[i]. Отсортируем пары по X.

Если у нас была бы одна куча, то ответ: X[0] * min(Y[i]).

Кучи две. Зафиксируем прямоугольник в каждой куче с самым мелким X. Первый — это 0, а по второму будем перебирать — пускай это будет i.

Тогда ответ будет: X[0] * min(Y в первой куче) + X[i] * min(Y во второй куче). По нашему определению, все прямоугольники 1..i-1 идут в первую кучу. То есть, 1 <= i <= N. Осталось разобраться с остальными i+1..2*N-1 прямоугольниками. Назовём Z такой прямоугольник из i+1..2*N-1, что его Y минимален. Тогда есть 2 варианта куда он пойдёт:

• В первую кучу. Тогда ответ первой кучи не может больше зависить от прямоугольников этой группы и мы добираем туда прямоугольников с как можно меньшими Y пока можем. Ответ: X[0] * min(min(Y в 0..i-1), Y[Z]) + X[i] * min(Y[i], (N-1)-ое наибольшее число в i+1..2*N-1)
• Во вторую кучу. Тогда ответ второй кучи не может больше зависить от прямоугольников этой группы и мы добираем туда прямоугольников с как можно меньшими Y пока можем. Ответ: X[0] * min(min(Y в 0..i-1), (N)-ое наименьшее число в i+1..2*N-1) + X[i] * min(Y[i], Y[Z])

min(Y в 0..i-1) можно преподсчитать, Z можно находить итерируя, а k-ое наименьшее/наибольшее число можно искать либо деревом отрезков, либо бинарными кучами.

Ну и надо аккуратно написать, не завалившись на всяких пограничных случаях (i = N, N = 1 и.т.п.).

Пожалуйста.

А еще можно слева от чата и "Who's here" (под "Rating key") нажать "Messages". Там есть все сообщения.

кроме как этого я предложить не могу...

но вот как до этого дойти, самому интересно)