MWC '15 #2 P4: Robotics Summative

View as PDF
Submit solution
Points: 5 (partial)
Time limit: 3.0s
Memory limit: 256M
Author:
MathBunny123
Problem type

Robotics (TER4M) is an intensive course at William Lyon Mackenzie CI, which requires students to program and design advanced machinery. atarw however prioritizes his top-6 marks, and doesn't quite put as much effort into the project. The ISP, worth 30% of the final mark, is supposed to pick up tennis balls and throw them over a wall where the opponent is also throwing tennis balls over. The player to throw the most tennis balls into the opponent's field during 2 minutes win.

However, atarw has a genius strategy. He's going to build rectangles using VEX pieces and block off all the opponent's shots. He is limited to using only rectangles, so there needs to be 2 pairs of equal sides or all equal sides. In addition, he also has time to cut off 1 cm if required off every piece to build a rectangle. Given N sticks, each with a maximum length of L, compute the total area of rectangles that can be built to shield the robot and not throw the balls over.

Input Specification

The first line will contain integers N (number of pieces), followed by N numbers indicating each respective length (separated by space).

Subtask 1 [25%]

1 \le N \le 4, 1 \le L \le 100

Subtask 2 [75%]

1 \le N \le 10^6, 1 \le L \le 10^6

Note: Fast input may be required.

Output Specification

Output the largest possible area.

Sample Input

4
2 2 4 5

Sample Output

8

Explanation

We can take the piece with 4 cm as the width, take the 5 cm piece and cut off 1 cm so it's also the width, and then take the 2 cm pieces as the height. The area is 4 \times 2 = 8.

Comments


  • 0
    aurpine  commented on March 26, 2016, 6:13 a.m.

    What do we output if there is no rectangle possible?