GAME02 - Game bắn bĩa
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Sau những giờ thi căng thẳng tại HDCity, BTC sắp xếp cho các thí sinh gặp nhau và tham gia các trò chơi giải trí. Trong nội dung bắn đĩa bay, trước khi vào vị trí bắn người chơi được BTC cho quan sát N đĩa, trên mỗi đĩa ghi một số nguyên dương tương ứng với điểm có được nếu người chơi bắn trúng. Súng để bắn đĩa là loại súng thể thao có hai nòng, tại mỗi thời điểm có thể nạp được tối đa 02 viên đạn, mỗi lần bóp cò chỉ bắn ra 01 viên đạn, sau khi bắn 01 viên đạn hoặc bắn 02 viên đạn vận người chơi có thể nạp lại đạn. Như vậy, khi hệ thống phóng đĩa hoạt động, người chơi chỉ bắn được tối đa hai đĩa gần nhau rồi phải thực hiện thao tác nạp đạn trước khi muốn bắn tiếp. Biết mỗi lần nạp đầy đạn thì ít nhất một đĩa đã bay qua tầm ngắm và vận động viên không thể bắn được những đĩa này.

Hãy viết chương trình giúp người chơi chọn một số đĩa để bắn sao cho tổng điểm thu được là lớn nhất. Giả sử tỷ lệ bắn trúng đĩa là 100%.

Yêu cầu: Cho N đĩa có ghi số điểm của đĩa tương ứng. Máy phóng đĩa sẽ phóng lần lượt từ đĩa thứ nhất đến đĩa thứ N. Hãy xác định tổng điểm lớn nhất mà người chơi đạt được.

Dữ liệu:  

  • Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 106).
  • Dòng thứ 2 chứa N số nguyên a[i] là số điểm ghi trên các đĩa (0 < a[i] ≤ 109).

Kết quả:

Đưa ra một số nguyên – số điểm lớn nhất tìm được.

Ví dụ

Input

4
9 3 5 4

Output

18

Giới hạn:

60% số tests ứng với 60% số điểm của bài có 1 ≤ N ≤ 100000 và 0 < a[i] ≤ 1000.


Nguồn: Nguyễn Tất Thành - Yên Bái

Back to Top