Robot chọn quà

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M

Tác giả:
Dạng bài

Cho lưới ô vuông gồm \(3\) hàng và \(N\) cột, ô ở hàng \(i\) và cột \(j\) được đặt một phần quà có giá trị \(A_{ij}\ (1\leq i\leq 2,\ 1\leq j\leq N,\ 1\leq A_{ij}\leq 10^9)\).

Một rô-bốt xuất phát từ ô \((1,\ 1)\) và di chuyển đến ô \((3,\ N)\) theo quy tắc sau:

  • Nếu rô-bốt đang đứng ở ô \((i,\ j)\) thì có thể di chuyển đến ô \((i + 1,\ j)\) hoặc \((i,\ j + 1)\);
  • Rô-bốt không được di chuyển ra khỏi lưới ô vuông.

Với mỗi đi qua, rô rô-bốt nhận được phần quà đã được đặt sẵn tại ô đó.

Yêu cầu: Tính tổng giá trị các phần quà mà rô-bốt có thể nhận được lớn nhất là bao nhiêu?

Input:

  • Dòng đầu ghi số nguyên dương \(N\);
  • Dòng thứ hai ghi \(N\) số nguyên \(A_{11},\ A_{12},\ldots ,\ A_{1N}\);
  • Dòng thứ ba ghi \(N\) số nguyên \(A_{21},\ A_{22},\ldots ,\ A_{2N}\);
  • Dòng thứ tư ghi \(N\) số nguyên \(A_{31},\ A_{32},\ldots ,\ A_{3N}\);
  • Các số trong tệp ghi cách nhau ít nhất một dấu cách.

Output: Một số nguyên duy nhất là tổng giá trị các phần quà lớn nhất mà rô-bốt có thể nhận được.

Ràng buộc:

  • Có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(1\leq N\leq 500\);
  • Có \(30\%\) số test tương ứng với \(30\%\) số điểm của bài thỏa mãn: \(1\leq N\leq 5000\);
  • Có \(40\%\) số test tương ứng với \(40\%\) số điểm của bài thỏa mãn: \(5000\leq N\leq 10^6\).

Ví dụ:

SAMPLE INPUT

5
3 2 2 4 1
1 2 2 2 1
1 1 1 1 1

SAMPLE OUTPUT

15

Giải thích: Rô-bốt đi qua các ô sau: \((1,\ 1);\ (1,\ 2);\ (1,\ 3);\ (1,\ 4);\ (2,\ 4);\ (2,\ 5);\ (3,\ 5)\).