Gửi bài giải

Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: BAI1.INP
Output: BAI1.OUT

Tác giả:
Nguồn bài:
CHV
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một số nguyên dương ~n~ và dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Một dãy con không kề nhau là dãy được tạo ra bằng cách chọn ra một số phần tử của dãy sao cho không có hai phần tử nào được chọn có vị trí ban đầu kề nhau.

Hãy chọn ra một dãy con không kề nhau sao cho thỏa mãn hai điều kiện sau:

  • Tổng các phần tử được chọn là một số lẻ;
  • Tổng các phần tử được chọn là lớn nhất có thể.

Input BAI1.INP

  • Dòng 1: chứa số nguyên dương ~n~ (~1 \le n \le 10^5~).
  • Dòng 2: chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).

Output BAI1.OUT

In ra một số nguyên là tổng lẻ lớn nhất tìm được. Nếu không tìm được dãy con thỏa mãn, in ~-1~.

Scoring

Subtask Điểm Ràng buộc
1 25% ~n \le 20~
2 35% ~n \le 2000~, ~a_i \le 1000~
3 40% Không có ràng buộc bổ sung

Sample Input 1

5
2 3 4 5 1

Sample Output 1

7

Notes

Chọn dãy ~\{2, 4, 1\}~ (các phần tử ở vị trí 1, 3 và 5) có tổng 7 là số lẻ và không có hai phần tử được chọn nào kề nhau. Đây là dãy có tổng lớn nhất thỏa mãn.


Đang tải...