USACO 2003 US Open Orange - Jumping Cows- 플라이투더문 > 문제은행 : 정보올림피아드&알고리즘




1778 : 플라이투더문

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
0 회   
시도횟수
2 회   

문제

농부 창호의 소들은 높이 날라서 달까지 닿고 싶어 하지만, 소 혼자 달까지 점프를 한다는 것은 누구 말 마따 로또 1등에 당첨되었다가 그것을 찾으러 갈때 벼락을 맞을 확률 보다 일어나기 힘든 일이다. 자신들의 상황을 슬퍼하는 것을 본 마술사 정택이는 P개의 점프를 하는데 도와주는 점프 포션을 소들에게 주었다.

 

마술사 정택이가 건네준 점프 포션은 정택이가 준 순서대로 사용을 할 수 있으며, 포션은 반드시 한번만 사용할 수 있으며, 어떤 것은 사용하지 않고 버릴 수 있다. 점프 포션은 각각 '힘'을 가지게 되는데, 이는 소가 점프를 할 때의 능력치에 변화를 준다.

 

소가 처음에 점프를 할 때의 도달 가능한 높이를 0이라고 하고, 처음 포션을 썼을 때는 포션의 힘만큼 점프가 가능하다. 두 번째 포션을 썼을 때는 두 번째 포션의 힘만큼 점프가 가능한 높이가 줄어들게 된다. 홀수 번째로 사용하게 되는 포션은 점프력에 더해지고, 짝수 번째로 사용하게 되는 포션은 점프력을 힘만큼 빼게 된다.

 

점프 포션들의 힘이 주어졌을 때, 농부 창호의 소들이 얼마나 높게 점프를 할 수 있는지 알아보는 프로그램을 작성하라.


입력형식

입력의 첫 번째 줄에는 포션의 개수 P(1≤P≤150,000)이 입력되며, 그 다음 줄에는 P개의 포션의 힘이 순서대로 들어온다. 포션의 힘은 1이상 500이하이다.


출력형식

주어진 포션을 가지고 가장 높게 뛸 수 있을 때의 점프력을 출력한다.


입력 예

8
7 2 1 8 4 3 5 6

출력 예

17


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP