Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MAXCUB - Khối lập phương lớn nhất

Cho một khối lập phương kích thước n chia làm n3 khối lập phương đơn vị. Mỗi khối lập phương đơn vị chứa 1 số nguyên.
Bạn hãy tìm một khối lập phương con của khối lập phương đã cho sao cho tổng các số trong khối lập phương con đó là lớn nhất.

Input

- Dòng đầu: số lượng test.
- Tiếp theo là các test, mỗi test gồm: dòng đầu là n. Sau đó n nhóm dòng thể hiện lớp cắt của hình lập phương nhìn từ mặt trước từ gần ra xa, mỗi nhóm gồm n dòng, mỗi dòng gồm n số liệt kê các số trên lớp cắt từ trên xuống dưới, trái qua phải.
Chú ý: n <= 30. Giá trị của khối lập phương đơn vị thuộc kiểu integer.

Output

Mỗi dòng chứa tổng của khối lập phương con lớn nhất của test tương ứng.

Example

Input:
2
3
0 -1 3
-5 7 4
-8 9 1
-1 -3 -1
2 -1 5
0 -1 3
3 1 -1
1 3 2
1 -2 1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Output:
27
64

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-14
Thời gian chạy:0.145s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2018-07-27 14:19:05
prefix 3 chiều nhé :)
http://123link.pw/JrwDOl
Các bạn tham khảo
2018-07-27 05:22:08
ChuBangNgoNghinh
2017-03-09 09:16:35
cũng dễ mà hị hị P:)
2016-10-08 13:17:08
Qua bài này mới biết được prefix sum có thể áp dụng cho không gian 3 chiều =))
2015-11-19 13:21:29 Do Hong Huan
Để làm được bài này mình phải lấy cục RUBIK ra để tưởng tượng :D
2015-09-08 14:12:36
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-06-13 11:17:56 [Nghien] Le Long
Đệ quy đặt cận AC =)))
2015-05-16 23:54:56 Stupid Dog
để dư dấu chấm phẩy trên công thức khi xuống dòng làm WA hoài
2013-08-30 14:10:11 a;slkfjasl;fkj
p/s nên cho biết bao nhiêu test để tính toán độ phức tạp chứ ạ :(
2009-05-19 21:21:24


Last edit: 2009-05-20 13:46:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.