콜라 나르기 > 문제은행

fff

1444 : 콜라 나르기

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
75 회   
시도횟수
229 회   

문제

영원이네 마을은 하나의 도로로 구성되어 있다.


이 일차원 도로에 마을들이 놓여 있다. 각 마을에는 콜라의 수요와 공급이 있다. 

다행히 영원이 마을의 수요와 공급은 합이 동일하다. 

그런데 콜라를 운반하는 데에는 비용이 필요한데, 

콜라를 한 마을에서 다른 마을에 공급할 때 운반하는 양과 거리의 곱만큼의 비용이 든다.


모든 콜라는 동일한 품질이기 때문에 콜라를 구입하는 데에는 우선순위가 없다.


마을들은 일차원 도로 위에 1의 거리 간격으로 일정하게 나열되어 있다고 가정한다.


입력형식

입력의 첫줄에는 마을의 수 n(2≤n≤100,000)이 입력된다.

다음 n줄에 걸쳐 각 마을의 수요 또는 공급이 정수 ai(-1 000≤ai≤1 000)로 입력된다. ai>0는 그 만큼을 구매하고자 함을 의미하며 ai<0 이면 그 절대값 만큼 팔려고 하는 것이다.


출력형식

전체 수요와 공급을 만족시키는 운반의 최소 비용을 출력하라. signed 64-bit integer의 자료형이 필요할 것이다.


입력 예

5
5 -4 1 -3 1

출력 예

9

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP