Problem hidden
MAXCUB - Khối lập phương lớn nhất
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/maxcub
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
Added by: | Nguyen Dinh Tu |
Date: | 2006-10-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |