Bản đồ thành phố là một bảng kích thước M x N, các cột được đánh chỉ số từ trái sang phải, các dòng được đánh chỉ số từ trên xuống dưới. Hiện nay thành phố đang bị ô nhiễm nặng, trên mỗi ô (i,j) (giao nhau bởi dòng i và cột j) có A[i,j] đơn vị rác thải.
Thị trưởng thành phố quyết định sử dụng một con robot đi thu gom rác ở các ô. Robot được lập trình chỉ đi theo hướng xuống dưới, tức là từ ô (i,j) robot chỉ có thể đi tới ô (i+1,j-1), (i+1,j) hoặc (i+1,j+1). Chính vì vậy để robot có thể thu gom được nhiều rác nhất thì người ta phải cho robot xuất phát từ dòng 1 và đi xuống dòng M.
Hãy xác định vị trí cột xuất phát tại dòng 1 và hành trình của robot sao cho robot có thể thu gom được nhiều rác thải nhất.
Dữ liệu vào từ file GARBAGE.INP:
Dòng thứ i + 2 ghi số L là cột mà robot sẽ đi trên hành trình từ dòng 2 tới dòng M
GARBAGE.INP |
GARBAGE.OUT |
5 4 4 5 2 4 3 4 5 2 3 4 5 2 5 6 3 5 4 5 2 5 |
26 2 3 3 2 2 |