Castle Invasion

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
PyPy 2 5.0s
PyPy 3 5.0s
Memory limit: 64M
PyPy 2 256M
PyPy 3 256M

Authors:
Problem type

Bob is planning an attack on a suspicious castle owned by the evil villain Joe! The castle can be thought of as an N by N grid of towers, with each tower having an integer height. To scout for this attack, Bob sent his only drone that can instantly transmit pictures to take photos of the castle. However, the drone only managed to take 2 photos before critically running out of battery and tumbling into the forest. One photo was taken of the front side of the castle, while the other captured its right side. It was also discovered (slightly too late) that the drone's camera cannot capture depth! Since Bob does not want to fail this attack, he would like to know the maximum possible volume of the castle, or if the photos are incorrect and a castle cannot be reconstructed. Can you help him find out?

Input Specification

The first line of the input will contain an integer N, representing the dimensions of the castle.

The second line will contain N integers c_i (1 \le i \le N), representing the height of the tallest tower in the ith column.

The third line will contain N integers r_j (1 \le j \le N), representing the height of the tallest tower in the jth row.

Output Specification

A single integer, representing the maximum possible volume of the castle, or -1 if it is impossible to reconstruct a castle.

Constraints

For all subtasks,
1 \le N \le 10^6
1 \le c_i, r_j \le 10^6

Subtask 1 [30%]

1 \le N \le 1\,000

Subtask 2 [70%]

No additional constraints.

Sample Input 1

4
1 3 4 2
2 2 1 4

Sample Output 1

28

Sample Input 2

4
1 2 6 2
5 3 3 3

Sample Output 2

-1

Explanation for Sample Output 2

No matter how you assign heights to each tower, it is impossible to reconstruct a castle that satisfies both photos.


Comments

There are no comments at the moment.