import java.util.Scanner;
public class Main
{
    public static void main(String[] args) {
        Scanner a = new Scanner(System.in);
        int x = a.nextInt();
        //String x1 = a.nextLine();
        int y = 0;
        int z = 0;
        int [] array1 = new int[x];
        for(int i=0;i<x;i++)
        {
            array1[i] = a.nextInt();
            y+=array1[i];

            if(i==1 && array1[i] < array1[i-1] )
                {
                    int tmp = array1[i];
                    array1[i] = array1[i-1];
                    array1[i-1] = tmp;
                }
        }

        for(int i=array1.length-1;i>-1;i--)
        {
            z+=array1[i]*y;
            y-=array1[i];
            z+=array1[i]*y;
        }

        System.out.println(z);
    }
}

sort the array. maintain W, the total weight of the array.
start from the smallest element and add A[i] * W to ANS.
subtract A[i] from W.
add A[i] * W again.

1. If time limit exceeded, use a better sorting algorithm. In my case, insertion sort spent barely over a second, while merge sort spent only 0.6 of a second.

2. used long long. Also, before multiplying a long long and an int together, convert the int first.

Is there any algorithm to be applied except sorting?

Если мы можем оставлять часть груза в городах(любое кол-во груза), то ответ будет 24(может и меньше). Ошибка в условии или некорректно сформулировано условие?

Let we visit towns by distance ascending: 1, 2, 3
So total fine is : (6+5) + (5*2+3*2) + 3 = 11 + 16 + 3 = 30
Where am I wrong?

Can anyone please explain the sample solution given in the problem

Edited by author 24.06.2019 13:55