HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


51149 - One Piece Arena

Guest
• Discussion of problem (2)

Section problems

• 50672 - Math and Soldiers
• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Arbi Elezi, 2nd year student, CP 3rd Edition, One Piece anime, Google. Difficulty Gamma

Bartolomeu has finally joined the Straw Hat's pirate fleet.
He is known for having powers that allow him to create impenetrable barriers of all shapes and sizes , however, the last battles have left him with strange after effects. He now can only use his powers once per day, and he can only create barriers in rectangular shapes. But the greatest problem he has is that he is now allergic to all fish-mans(half fish, half men creatures), which inflict damage on him on contact.

Unfortunately, Bartolomeu got kidnapped by the evil fish-man pirate captain John Haddock and is forced to fight in square shaped arena full of fish-men and monsters. Each square unit of the area is either empty, or is filled with combination of beasts and fishmen. Fortunately, Bartolomeu has a radar which tells him how much damage can each unit square inflict on him, or how much damage, he can inflict on them. It is known that the squares that Bartolomeu damages, appear with positive integers, while the squares that damage Bartolomeu, appear with negative value.

Since Bartolomeu is not good at maths, he wants you to create a program that tells him the maximum gross damage he can inflict.

The gross damage is the total of positive and negative integers in the area that he chooses to cover

If the gross reaches less than -9999, Bartolomeu dies.



Input Specifications:

You will be first given an integer n: 2<= n <= 100, which represt the dimensions of the area. Then you will be given n^2 integers d separated by white spaces: -9999 <= d <= +9999, which represent the damage on each unit square of the area



Output Specificartions:

You have to show one integer(possibly long long, or long for Java Users),which represents the maximum gross damage that Bartolomeu can inflict!
If the gross damage is less than -9999, output "Fatality!" instead, without double quatations.



Sample input:
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2


Sample output:
15



Hint: He chooses to attack the sub-rectangle that starts at position y = 2;x = 1 and ends at position y = 4; x = 2; since he can attack only once by creating a rectangular shape barrier



maximum_gross_damage = 9 + 2 +(-4) +1 +(-1) + 8 = 15;

Для отправки решений необходимо выполнить вход.

www.contester.ru