시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 148 64 52 45.217%

문제

벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이의 거리는 1로 모두 동일하다. 사람들은 움직이지 않고 모든 벼룩 배달을 배달부 기영이에게 맡긴다. 기영이가 두 사람 사이에 벼룩을 배달하는 비용은 (벼룩의 수) * (두 사람 사이의 거리)이다. 모든 벼룩을 사려는 사람에게 배달했을 때, 기영이가 벼룩을 가장 저렴하게 배달하는 비용은 얼마인지 알아보자.

위 예시의 3번 사람은 벼룩 400개를 구하고자 하고, 1번 사람은 500개를 팔고자 한다. 이때 3번 사람이 1번 사람의 벼룩 400개를 살 경우, 벼룩을 옮기는데 드는 비용은 (두 사람 사이의 거리) 2 × (배달하는 벼룩의 수) 400 = 800이 된다.

기영이가 1번 사람에게서 2번 사람에게로 벼룩 200개를 배달하고, 1번, 4번, 5번 사람에게서 3번 사람에게로 각각 300개, 50개, 50개를 배달하면 최소 배달 비용은 200 + 300 × 2 + 50 + 50×2 = 950이다.

입력

첫째 줄에 시작에 존재하는 가게의 개수 N (1 ≤ N ≤ 100,000)가 주어진다.

둘째 줄부터 N+1번 줄까지 각 사람이 거래하려는 벼룩의 수 L (-1000 ≤ L ≤ 1000)이 순서대로 주어진다. L이 양수일 경우 벼룩을 파는 사람이며, 음수일 경우 벼룩을 사는 사람이다.

출력

기영이가 벼룩을 전부 배달하는 최소 비용을 출력한다. 출력값은 최대 263-1이며, 이 경우 int 범위를 초과하기 때문에 int 대신 long long을 사용해 출력한다.

예제 입력 1

5
500 -200 -400 50 50

예제 출력 1

950

예제 입력 2

6
1000 1000 1000 -1000 -1000 -1000

예제 출력 2

9000

출처

University > 서강대학교 > 2017 Sogang Programming Contest - Champion A번

  • 잘못된 조건을 찾은 사람: ntopia
  • 문제를 만든 사람: twinstar