Woburn Challenge 2002 - Suicidal

Problem 1: Dark Lord

The showdown with Sauron was at hand. Dwarfs, humans, hobbits, elves and all other creatures of Middle-earth like a huge cloud moved over the bad lands of Mordor towards the castle.

Then, he stepped outside. With his huge sword he slashed left, right and as he does he swept away tens - no hundreds. His strikes precise and vicious.... "Just how does he do it?" slipped through Elrond's head. Gandalf, as though reading his thoughts, explained: "When the Dark Lord strikes, he sweeps what is roughly a cuboid. Through the eyes of the ring he sees the total number of creatures and weapons in each one by one by one square. Note that the squares stack up and down as well as horizontally, due to the various heights of the creatures. Next, Sauron evaluates the optimal target box, and attacks...."

Elrond's eyes lit up in the dark, stench-filled Mordor sky. "We can use this against him. We will distribute our people so as to minimize the damage he can do. First we need to calculate the maximum damage in any rectangular prism. Then...."

Elrond gasped as the legions near him were struck to oblivion by another carefully placed Sauron blow. Elrond himself fell to the blow, badly wounded.
It was all up to the little human, then, to calculate the damage as prescribed...

Calculate the maximum damage Sauron can achieve given his maximum strike area - a cube of dimensions A x A x A, A ≤ 30. Note that the maximum strike area will be a cuboid (a.k.a. rectangular pism a.k.a. right prism a.k.a. rectangular parallelepiped a.k.a. box) within the latter.

At each square within the box there will be an integer corresponding to the number of creatures, weighted by strength, minus the number of weapons, again weighted by strength (note that this number will be in the range [-10000..10000]). Each creature's weight and beer drinking habits are also compensated for. The cube will be input layer by layer, starting from the top. Any partial sum will fit within a signed 32-bit integer.

Input

Each case starts with a single integer, A.
[cube, layer by layer]

There will be multiple test cases; the cases will end when A = -1.

Output

The maximum damage Sauron can inflict.

Sample Input

3
1 1 1
1 1 1
1 1 1
-10 -10 -10
-10 -10 -10
-10 -10 -10
2 2 2
2 2 2
2 2 2
-1

Sample Output

18

All Submissions
Best Solutions

Point Value: 25
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 05, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)