[Python_Training] Vết của ma trận

Xem PDF
Tác giả:
jumptozero
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 550 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

  • Cho ma trận \(A\) có kích thước \(n\text { x }n\) với \(n\in \mathbb{N}^{*}\)

  • Vết của ma trận \(A\) có kí hiệu là \(tr(A)\) và được định nghĩa như sau: \(tr(A)=\sum\limits_{i=1}^{n}A[i][i]\) (tổng các phần tử trên đường chéo chính).

Xét tất cả các ma trận vuông con (của ma trận \(A\)) có kích thước \(k\text{ x }k\) (bằng cách bỏ đi một số hàng( hoặc không bỏ hàng nào) và một số cột (hoặc không bỏ cột nào) của ma trận \(A\) ) với \(1\le k\le n\), hãy tìm ma trận con có vết lớn nhất và in giá trị đó ra màn hình.

Input

  • Dòng thứ nhất chứa hai số nguyên \(n,k(1\le n\le 50;1\le k\le n)\)

  • \(n\) dòng tiếp theo, mỗi dòng là một chuỗi gồm \(n\) kí tự số (\('0'..'9'\))

Output

  • In ra kết quả thỏa mãn yêu cầu bài toán.

Example

Test 1

Input 
3 3
123
456
789
Output 
15
Note

Test 2

Input 
5 3
12689
55555
55555
55555
55555
Output 
16
Note

Test 3

Input 
3 2
233
111
233
Output 
6
Note

Giải thích: Ở ví dụ 3, ta bỏ đi hàng \(2\) và cột \(1\). Ta sẽ còn lại ma trận con \(2\times 2\) có vết lớn nhất là \(6\). Còn ở ví dụ \(4\), ta bỏ đi các cột \(1,2\) và các hàng \(2,4\). Khi đó ta thu được ma trận \(3\times 3\) có vết lớn nhất là \(9\)

Test 4

Input 
5 3
23333
11111
23333
11111
23333
Output 
9
Note

Bình luận