농부 존에게는 한 줄을 이루는 N개의 잔디밭이 있는데 (1 <= N <= 2 X 105), i번 잔디에는 건강한 잔디와 비교했을 때 박테리아가 ai만큼 더 있습니다 (-1015 <= ai <= 1015). 예를 들어 ai = -3이면 i번 잔디는 정상보다 박테리아가 3만큼 적기 때문에 건강해지기 위해서는 3만큼 박테리아를 추가해야 합니다.
농부 존은 모든 잔디밭이 건강한 수준의 박테리아를 가지도록 고치고 싶습니다. 편하게도 존에게는 밭에 뿌릴 수 있는 두 종류의 농약이 있는데, 하나는 박테리아를 더하고 하나는 박테리아를 없앱니다. 농부 존이 농약을 뿌릴 때는, (가장 오른쪽이 되는) N번 잔디에 서서 분사기의 힘 L을 정합니다 (1 <= L <= N).
분사기는 농부 존에 가까운 밭에 가장 큰 영향을 주며 멀어질수록 그 영향이 줄어듭니다. 만약 농부 존이 박테리아를 더하는 농약을 골랐다면 N번 잔디에는 L만큼, N-1번 잔디에는 L-1만큼, N-2번 잔디에는 L-2만큼과 같은 방식으로 박테리아가 더해집니다. 분사기의 힘이 충분히 강하지 않아 닿지 않는 1 ~ N-L번 잔디에는 박테리아가 더해지지 않습니다. 유사하게 농부 존이 박테리아를 제거하는 농약을 골랐다면 N번 잔디에는 L만큼, N-1번 잔디에는 L-1만큼과 같은 방식으로 박테리아가 제거됩니다. 마찬가지로, 1 ~ N-L번 잔디는 영향을 받지 않습니다.
모든 잔디밭이 건강한 잔디의 박테리아 값을 가지기 위해 농부 존이 분사기를 사용해야 하는 최소 횟수를 구합시다. 정답은 최대 109임이 보장됩니다.
이 문제에 사용되는 정수의 크기가 커 (C/C++의 "long long"과 같은) 64비트 자료형을 사용해야 할 수도 있음에 유의합시다.
입력
첫 줄에 N이 주어집니다.
두 번째 줄에 각 잔디의 초기 박테리아 양을 나타내는 N개의 정수 a1 ~ aN이 주어집니다.
출력
모든 잔디가 건강한 잔디를 나타내는 박테리아 권장 값을 가지기 위해 필요한 최소 분사 횟수를 출력합니다.
ez_code 2년 전
문제
농부 존에게는 한 줄을 이루는 N개의 잔디밭이 있는데 (1 <= N <= 2 X 105), i번 잔디에는 건강한 잔디와 비교했을 때 박테리아가 ai만큼 더 있습니다 (-1015 <= ai <= 1015). 예를 들어 ai = -3이면 i번 잔디는 정상보다 박테리아가 3만큼 적기 때문에 건강해지기 위해서는 3만큼 박테리아를 추가해야 합니다.
농부 존은 모든 잔디밭이 건강한 수준의 박테리아를 가지도록 고치고 싶습니다. 편하게도 존에게는 밭에 뿌릴 수 있는 두 종류의 농약이 있는데, 하나는 박테리아를 더하고 하나는 박테리아를 없앱니다. 농부 존이 농약을 뿌릴 때는, (가장 오른쪽이 되는) N번 잔디에 서서 분사기의 힘 L을 정합니다 (1 <= L <= N).
분사기는 농부 존에 가까운 밭에 가장 큰 영향을 주며 멀어질수록 그 영향이 줄어듭니다. 만약 농부 존이 박테리아를 더하는 농약을 골랐다면 N번 잔디에는 L만큼, N-1번 잔디에는 L-1만큼, N-2번 잔디에는 L-2만큼과 같은 방식으로 박테리아가 더해집니다. 분사기의 힘이 충분히 강하지 않아 닿지 않는 1 ~ N-L번 잔디에는 박테리아가 더해지지 않습니다. 유사하게 농부 존이 박테리아를 제거하는 농약을 골랐다면 N번 잔디에는 L만큼, N-1번 잔디에는 L-1만큼과 같은 방식으로 박테리아가 제거됩니다. 마찬가지로, 1 ~ N-L번 잔디는 영향을 받지 않습니다.
모든 잔디밭이 건강한 잔디의 박테리아 값을 가지기 위해 농부 존이 분사기를 사용해야 하는 최소 횟수를 구합시다. 정답은 최대 109임이 보장됩니다.
이 문제에 사용되는 정수의 크기가 커 (C/C++의 "long long"과 같은) 64비트 자료형을 사용해야 할 수도 있음에 유의합시다.
입력
첫 줄에 N이 주어집니다.
두 번째 줄에 각 잔디의 초기 박테리아 양을 나타내는 N개의 정수 a1 ~ aN이 주어집니다.
출력
모든 잔디가 건강한 잔디를 나타내는 박테리아 권장 값을 가지기 위해 필요한 최소 분사 횟수를 출력합니다.