Задача №112839. Торговый центр
В стране Олимпии решили построить большой торговый центр. Для этого был выделен квадратный участок N × N метров. Существуют определенные ограничения касательно высоты здания. А именно: если разбить схему участка на вертикальные и горизонтальные полоски шириной 1 метр, то здание в пределах одной полоски будет иметь заданное ограничение на высоту. Архитекторы хотят построить торговый центр в форме прямоугольного параллелепипеда. Напишите программу, которая по данным о размере участка и ограничения по высоте для каждой из полосок найдет максимальный объем здания в форме прямоугольного параллелепипеда, которое можно построить на данном участке.
Входной файл состоит из трех строк. В первой строке содержится натуральное число N (2 ≤ N ≤ 5 × 10 4 ) — размер участка. Вторая строка содержит N неотрицательных целых чисел, каждое из которых не превышает 10 5 , — ограничение высоты по вертикальным полоскам. Третья строка содержит N неотрицательных целых чисел, каждое из которых не превышает 10 5 , — ограничение высоты по горизонтальным полоскам.
Выходной файл должен содержать единственное число — максимальный объем здания торгового центра, которое можно построить на заданном участке. Входные данные гарантируют возможность построить на участке здание ненулевого объема.
Набор тестов состоит из 5 блоков, для которых дополнительно выполняются следующие ограничения:
- 10 баллов: 1 ≤ N ≤ 10
- 10 баллов: 10 < N ≤ 30
- 10 баллов: 30 < N ≤ 70
- 30 баллов: 70 < N ≤ 1000
- 40 баллов: 1000 < N ≤ 5 × 10 4
3 0 1 0 0 2 0
1
3 3 2 1 1 2 3
9