LCC '18 Contest 1 S2 - Hoverboard

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Marty is trying to build a hoverboard for his engineering class. To accomplish this feat, he has decided to use electromagnetic levitation.

Marty has N charged coins at his disposal. He will split a subset of his coins into pairs and, for each pair, he will place one coin on a platform and the other coin on the hoverboard. He hopes that the coins will repel each other, causing his hoverboard to rise off the platform.

Marty is hoping to impress his teacher, so he wants his hoverboard to rise as high as possible. Help Marty determine the maximum force that he can exert on the hoverboard using N charged coins.

For two coins of charge q_1 and q_2, we say the force between them is equal to the product F=q_1q_2. The force between coins that are not paired up is negligible, so we will only consider the forces between the chosen pairs of coins.

Input Specification

The first line of input contains an integer N (1 \le N \le 100), the number of charged coins that Marty has. The next line contains N integers q_1, q_2, \ldots, q_N (-1000 \le q_i \le 1000), the charge of each coin.

Output Specification

The maximum total force that Marty can exert on the hoverboard using some pairing of coins.

Sample Input 1

4
1 2 3 4

Sample Output 1

14

Sample Input 2

5
-3 -2 1 4 5

Sample Output 2

26

Comments

There are no comments at the moment.