Chọn ô trên bảng hai hàng đạt tổng lớn nhất

Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved