시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 381 | 192 | 143 | 50.709% |
벼룩시장에서 사람들이 벼룩을 사고 판다. 놀랍게도 각 사람들이 사려고 하는 벼룩의 합과 파는 벼룩의 합은 같다. 벼룩을 사거나 파는 사람들은 서로 일렬로 길게 서 있으며, 인접한 가게 사이의 거리는 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)가 주어진다.
둘째에는 각 사람이 거래하려는 벼룩의 수 L (-1000 ≤ L ≤ 1000)가 순서대로 주어진다. L이 양수일 경우 벼룩을 파는 사람이며, 음수일 경우 벼룩을 사는 사람이다.
기영이가 벼룩을 전부 배달하는 최소 비용을 출력한다. 출력값은 최대 263-1이며, 이 경우 int 범위를 초과하기 때문에 int 대신 long long을 사용해 출력한다.
5 500 -200 -400 50 50
950
6 1000 1000 1000 -1000 -1000 -1000
9000
University > 서강대학교 > 2017 Sogang Programming Contest > Champion A번