COCI '21 Contest 4 #1 Autići

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There are n friends. Each friend has a remote control toy car and a garage in which the car is stored. Every friend also has a pack of road parts used to build the track for the cars. All the road parts in the i^\text{th} friend's pack have the same length d_i.

Two different friends a and b may connect their garages with a road. To build this road, they will both take a road part from their pack and join them, obtaining a road of length d_a + d_b. Some pairs of friends are going to connect their garages in the described way, so that everyone's garages are connected. In other words, starting from any garage it should be possible to reach any other garage using the roads.

What is the minimum total road length needed to make a road network in which all the garages are connected?

Input Specification

The first line contains a positive integer n (1 \le n \le 100\,000), the number of friends.

The next line contains n positive integers d_i (1 \le d_i \le 10^9), the length of the road parts in the i^\text{th} friend's pack.

Output Specification

In the only line, print the minimum total road length needed to make all the garages connected.


110d_1 = d_2 = \dots = d_n
2201 \le n \le 1\,000
320No additional constraints.

Sample Input 1


Sample Output 1


Explanation for Sample Output 1

Since there is only one friend, his garage is already connected to itself, so there is no need for building any roads.

Sample Input 2

5 5 5

Sample Output 2


Sample Input 3

7 3 3 5

Sample Output 3


Explanation for Sample Output 3

If roads are built between friends 1 and 2, 2 and 3, and between 3 and 4, everyone will be connected, and the total cost will be (7 + 3) + (3 + 3) + (3 + 5) = 24.


There are no comments at the moment.