Informatica Online Judge

  소들의 울음소리 [0457 / 01C9]

Time Limit(Test case) : 100(ms)
Number of users who solved : 77   Total Tried : 462


The Champion of this Problem (C++) : gs17033 - 0ms / 897byte
My Best Submission (C++) : N/A

[]

Background

n마리의 소가 일렬로 풀을 뜯고 있다. 그럼에도 불구하고 같은 자리에서 풀을 뜯는 소가 있기는 하다. 이 소들끼리는 대화를 하는데, 어떤 두 소가 대화하기 위해서는 두 소가 떨어진 거리만큼 소리를 높여서 대화를 해야 한다.
문제는 모든 소가 다른 소와 대화하기 위하여 높여야 하는 소리 크기의 합을 구하는 것이다.
n마리의 소가 있으므로, 총 n*(n-1)/2쌍의 대화가 이루어질 것이다. 예를 들면, 5마리의 소가 1, 5, 3, 2, 4의 위치에 있다면, 1번 소가 다른 소와 대화하기 위해 필요한 소리 크기의 합은 1+2+3+4=10이며, 2번 소는 5번 위치에 있으므로 4+3+2+1=10이 필요하다. (나머지 소에 대해서도 마찬가지로 구한다)

Input

첫 줄에 소의 n수 이 주어진다.
다음 n개의 줄에 걸쳐 소들의 위치 ai가 주어진다.
(1<=n<=10,000, 1<=ai<=1000)

Output

모든 쌍의 소들이 대화하기 위해 필요한 소리의 총합을 출력한다.

IO Example

입력
5
1
5
3
2
4

출력
40

문제출처 : USACO
데이터 출처 : 윤형석(서울대 컴퓨터공학과, 2009 IOI 금메달)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]