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
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
2009-05-19 20:54:49
Sao lại ko nhỉ :-/. Với các HĐH mà thường hay sử dụng, khi ko có chỉ dẫn biên dịch thì FPC sẽ mặc định integer ánh xạ vào SmallInt (16 bit). Khi đó, dĩ nhiên là con số ta phải sư dụng đối với bài trên chỉ nằm trong khoảng 32 bit.
Còn nếu với các HĐH khác, integer sẽ ánh xạ vào LongInt (32bit) thì con số ta phải làm việc với bài trên sẽ là 64bit.
Nó ảnh hưởng đến dung lượng bộ nhớ mà bài toán phải sự dụng và kéo theo một chú speed !!!.....

Last edit: 2009-05-19 20:56:25
2009-05-17 19:41:03 Khúc Anh Tuấn
Rất tiếc nó không làm ảnh hưởng gì đến bài toán cả :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.