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.|

AL_06_05 - Dobra i zła energia

Dobra i zła energia

    Jasiu posiada sporo działek i na każdej z nich postanowił wybudować dom, który będzie miał jak najwięcej pozytywnej energii. Jasiu swoje działki podzielił na jednostkowe pola prostokątne i poprosił o pomoc różdżkarza, by ten sprawdził każdą działkę i każdemu polu jednostkowemu przypisał wartość dobrej bądź złej energii. Różdżkarz swoją niezawodną różdżką każdemu polu przyporządkował pewną wartość (dodatnią, ujemną lub zero) w zależności od rodzaju i siły energii w tym miejscu. Jasiu mając te dane w postaci kwadratowej macierzy postanowił, że wybuduje dom na takim terenie prostokątnym złożonym z jednostkowych pól, w którym suma wartości energii wszystkich pól tego terenu będzie możliwie największa. Pomóż Jasiowi wyznaczyć te sumy na wszystkich jego działkach, a on już sam zajmie się budową domów.

Wejście
W pierwszym wierszu znajduje się wejścia liczba d działek Jasia (2 ≤ d ≤ 100)
Dla każdej działki w osobnym wierszu podana jest jedna liczba n (2 ≤ n ≤ 100) - wymiar podzielonej na jednostkowe pola działki.
Dalej n wierszy, w każdym wierszu n liczb całkowitych aij (-100 ≤ aij ≤ 100), gdzie aij to wartość energii w danym polu jednostkowym.

Wyjście
Na wyjściu należy wypisać d wierszy, w każdym wierszu jedna liczba całkowita - największa możliwa suma wartości energii wyznaczona przez pewien prostokątny obszar działki.

Przykład

Wejście
2
3
11 -2 3
-7 0 -6
2 8 3
5
5 2 -18 6 5
-2 3 1 -8 2
7 -7 3 4 11
-6 2 4 1 -5
7 7 -9 -8 6

Wyjście
13
20

Wyjaśnienie
Szary kolor wyznacza prostokątny obszar o największej sumie wartości energii odpowiednio na pierwszej działce równej 13 i na drugiej równej 20.

11 -2 3
-7 0 -6
2 8 3
5 2 -18 6 5
-2 3 1 -8 2
7 -7 3 4 11
-6 2 4 1 -5
7 7 -9 -8 6

Dodane przez:Mariusz Śliwiński
Data dodania:2013-05-01
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2013-05-11 10:28:09 Mariusz ¦liwiñski
Nie
2013-05-11 10:26:10 Damian Straszak
CZy pusty obszar pod dom jest dozwolony?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.