Untitled
unknown
plain_text
2 years ago
1.9 kB
2
Indexable
Hugo và chị ong nâu là hàng xóm của nhau. Tuy nhiên Hugo thì lười nhưng lại muốn lấy mật ăn, còn chị ong nâu thì chăm chỉ kiếm mật để đầy tổ của mình. Vì thèm ăn mật ong mà mãi chị ong nâu không cho nên sau 1 thời gian nằm gai nếm mật rình mò Hugo đã phát hiện ra các bố trí của các thùng chứa mật và số mật trong mỗi thùng ở nhà chị ong nâu. Mật ở nhà chị ong nâu được biểu diễn bằng 1 ma trận NxM ô, mỗi ô một thùng mật. Mỗi ô chứa lượng mật nhất định và có thể liên kết với 6 ô xung quanh theo cách bố trí của tổ ong. 2 ô được gọi là có liên kết nếu chúng có chung cạnh. Hôm nay Hugo phát hiện chị ong nâu đi sang khu rừng bên cạnh để lấy mật. Hugo sẽ vào nhà chị ong nâu để ăn trộm mật ong của chị. Để không bị phát hiện Hugo chỉ có thể lấy tối đa 4 thùng ở 4 ô có liên kết với nhau. Hãy giúp Hugo tìm ra bình phương tổng lượng mật lớn nhất có thể lấy. Ex: M = 5 , N = 3 Trong ví dụ trên, bình phương tổng lượng mật là (300 + 410 + 185 + 95)2 = 980100 Trong ví dụ trên Hugo sẽ bị phát hiện và không thể lấy mật. [Input] - Dòng đầu tiên là số thử nghiệm T (T <= 50) - Mỗi TC : + Dòng đầu tiên chưa kích thước ma trận M, N ( 3 ≤ N, M ≤ 15 ) + Trong N dòng tiếp theo, lượng mật C ở mỗi ô sẽ được cho theo quy tắc bên dưới (0 ≤ C ≤ 1000) 5 5 3 300 410 150 55 370 120 185 440 190 450 165 70 95 420 50 5 5 356 55 41 453 12 401 506 274 506 379 360 281 421 311 489 425 74 276 371 164 138 528 461 477 470 [Output] Ghi ra bình phương tổng lượng mật Case #1 2250000 Case #2 3748096 Case #3 3928324 Case #4 7236100 Case #5 13104400
Editor is loading...