Chọn ô trên bảng hai hàng đạt tổng lớn nhất
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một bảng số kích thước $2 \times N$ gồm các số nguyên (có thể âm). Bạn được phép chọn một tập các ô trên bảng sao cho không có hai ô nào được chọn kề cạnh nhau (chung cạnh ngang hoặc dọc).
Hãy tìm tổng giá trị lớn nhất của tập các ô được chọn (bạn có thể không chọn ô nào, khi đó tổng bằng $0$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Hai dòng tiếp theo, mỗi dòng chứa $N$ số nguyên mô tả các hàng của bảng ($|A_{r,c}| \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là tổng lớn nhất tìm được.
Ví dụ
| Input | Output |
|---|---|
| 4 1 5 2 3 4 2 8 1 |
20 |
Giới hạn
- $1 \le N \le 10^5$
- $|A_{r,c}| \le 10^9$
Community Discussion