#1478. BONUS - Phần thưởng

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Hồng là người thắng cuộc trong cuộc thi “Xây dựng Hệ thống chống dịch COVID-19” và được nhận phần thưởng của Ban tô chức. Ban tổ chức chuẩn bị một bảng kích thước m \times n . Các dòng của bảng được đánh số từ 1 đến m , từ trên xuống dưới. Các cột của bảng được đánh số từ 1 đến n , từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó ghi một số nguyên có giá trị a_{ij}\ (1 \le i \le m; 1 \le j \le n) .

Để nhận phần thưởng Hồng được phép chọn một dãy gồm ít nhất ba ô (i_1,j_1), (i_2, j_2),\ldots, (i_k,j_k) thỏa mãn:

  • Độ dài đoạn thẳng nối giữa tâm của hai ô (i_p, j_p) (i_{p+1},j_{p+1}) nhỏ hơn độ dài đoạn thắng nói giữa tâm của hai ô (i_{p+1},j_{p+1}) (i_{p+2},j_{p+2}) với mọi 1\le p \le k-2 ;
  • Gọi s là tổng tất cả các số trong các ô của dãy, số tiền mà Hồng nhận được là giá trị tuyệt đối của s . Các ô của dãy có thê được lặp lại và đương nhiên sẽ được tính tổng mỗi lần lặp lại.

Yêu cầu: Hãy giúp Hồng tính giá trị |s| lớn nhất có thể.

Dữ liệu vào:

  • Dòng thứ nhất chứa hai số nguyên dương n,m\ (m \times n \ge 4) ;
  • Dòng thứ i\ (1 \le i \le m) trong m dòng tiếp theo chứa n số nguyên a_{i1}, a_{i2}, \ldots, a_{in}\ (|a_i| < 10^9 .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là giá trị |s| lớn nhất có thể chọn được.

Ví dụ:

Dữ liệu vào:

1 4 
-1 2 3 4 

Dữ liệu ra:

10

Giải thích:

  • Các ô được chọn (1,4),(1,3),(1,1),(1,4) .

Giới hạn:

  • 30\% số test ứng với 30\% số điểm của bài có m=1;n \le 10 ;
  • 30\% số test khác ứng với 30\% số điểm của bài có m = 1; n \le 200 ;
  • 20\% số test khác ứng với 20\% số điểm của bài có m = 1;n \le 2000 ;
  • 20\% số test còn lại ứng với 20\% số điểm của bài có m x n \le 5000 .