발전소와 공장
면접 대비시간 제한2초메모리 제한1024 MB
일렬로 놓인 n개 도시에서 발전소와 공장을 인접한 구간으로 잇되, 모든 공장의 수요를 채우는 최소 총 길이를 구합니다.
문제
실업률 상승을 막기 위해 바이토시아 정부가 새로운 일자리를 만들기로 했다. 이를 위해 현대식 공장을 짓고, 공장에 전기를 공급할 새 발전소도 세운다.
바이토시아를 가로지르는 긴 고속도로가 있고, 그 옆으로 n개의 도시가 있다. 도시는 1부터 n까지 번호를 매긴다. 각 도시는 바로 앞 도시와 1킬로바이트미터 떨어져 있다.
일부 도시에는 공장이, 다른 도시에는 발전소가 세워질 예정이다. i번째 도시의 값 a_i가 주어진다. a_i가 양수이면 i번째 도시에 전력 생산량 a_i메가와트의 발전소가 세워진다. a_i가 음수이면 그 도시에 -a_i메가와트를 소비하는 공장이 세워진다. a_i = 0이면 그 도시에는 아무것도 짓지 않는다.
발전소에서 공장으로 전기를 보낼 전력망을 설계해야 한다. 인접한 도시 각 쌍에 대해 그 사이에 전력선을 놓을지 정한다. 전기는 발전소가 있는 도시와 공장이 있는 도시가 전력선으로 직접 또는 간접 연결되어 있으면 흐를 수 있다. 모든 공장의 전력 수요가 충족되면 전력망이 올바르게 설계된 것이다. 전력망의 비용은 전력선 길이의 합(킬로바이트미터 단위)에 정비례한다.
가장 저렴한 올바른 전력망을 설계하는 프로그램을 작성하라.
입력
첫째 줄에 도시의 수 n이 주어진다 (1 \le n \le 500 000).
둘째 줄에는 각 도시 건물의 전력 생산량 또는 소비량을 나타내는 정수 a_1, \ldots, a_n이 주어진다 ().
출력
올바른 전력망 중 가장 저렴한 비용을 한 줄에 출력한다. 올바른 전력망이 존재하지 않으면 -1을 출력한다.
힌트
그림은 n = 17개의 도시로 이루어진 테스트 케이스이다. 흰색 원 3개는 공장, 검은색 원 4개는 발전소이다. 회색 선분은 길이 12킬로바이트미터의 올바른 전력망을 나타낸다.
