Bedao Mini Contest 17 - PLUS

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một ma trận ~a~ kích thước ~n \times m~, tìm hai dấu cộng không có điểm chung trên ma trận sao cho tổng giá trị nằm trên hai dấu cộng là lớn nhất.

Một dấu cộng là hai đoạn thẳng có độ dài lẻ và bằng nhau, một đoạn thẳng nằm ngang, một đoạn thẳng nằm dọc và giao nhau tại trung điểm.

image
Ảnh ví dụ.

Các hình màu xanh là dấu cộng, màu vàng không phải là dấu cộng.

Input

  • Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ lần lượt là số hàng và số cột của ma trận ~a~ ~(2 \le n, m \le 15)~

  • Trên ~n~ dòng sau, dòng thứ ~i~ chứa ~m~ số nguyên, số thứ ~j~ miêu tả ~a_{ij}~, giá trị của ô hàng ~i~ cột ~j~ ~(-10^6 \le a_{ij} \le 10^6)~

Output

  • In ra trên một dòng một số nguyên duy nhất là kết quả của bài toán.

Subtask

  • ~30\%~ số test có ~n, m \leq 3~.

  • ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3 3
2 1 1
1 2 1
1 -1 -1

Sample Output 1

6

Note

Chọn hai dấu cộng sau:

  • Dấu cộng thứ nhất có tâm ở đỉnh ~(2,2)~ và có độ lớn là ~3~ (độ lớn ở đây là độ dài của ~2~ đoạn thẳng trong dấu cộng đó). Tổng các phần tử nằm trong dấu cộng này là ~2+1+1+1+(-1)=4~.

  • Dấu cộng thứ hai có tâm ở đỉnh ~(1,1)~ và có độ lớn là ~1~. Tổng các phần tử nằm trong dấu cộng này là ~2~.

Từ đó tổng tất cả các phần tử khi chọn cả ~2~ dấu cộng trên là ~4+2=6~. Có thể thấy được không có cách để chọn ~2~ dấu cộng ra tổng lớn hơn trong trường hợp trên.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.