콜라 나르기 > 문제은행

본문 바로가기


실전대비 Level5

1444 : 콜라 나르기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 55 회    시도횟수: 195 회   



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


이 일차원 도로에 마을들이 놓여 있다. 각 마을에는 콜라의 수요와 공급이 있다. 다행히 영원이 마을의 수요와 공급은 합이 동일하다. 그런데 콜라를 운반하는 데에는 비용이 필요한데, 콜라를 한 마을에서 다른 마을에 공급할 때 운반하는 양과 거리의 곱만큼의 비용이 든다.


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


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


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

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



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


[Copy]
5
5 -4 1 -3 1
[Copy]
9



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.