W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Nad Bajtołami Dolnymi przeszła zamieć. Ulice zostały pokryte wieloma metrami śniegu, a prognoza na najbliższe dni zapowiada mróz. Wszystko wskazuje na to, że jeszcze przez wiele dni mieszkańcy spędzą sporo czasu w swoich domach.
W tej sytuacji Bajtazar postanowił zająć się rozwiązywaniem następującego problemu algorytmicznego, który znalazł w Głosie Bajtołów. Dana jest macierz (tj. tabelka) liczb całkowitych. Należy znaleźć takie nienachodzących na siebie prostokątnych podtablic tej macierzy, że suma liczb w tych podtablicach jest jak największa. Każda z podtablic musi zawierać co najmniej jedną komórkę. Napisz program, który rozwiąże problem, z którym walczy Bajtazar.
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite , i (, ) oznaczające odpowiednio wysokość i szerokość macierzy oraz liczbę poszukiwanych podtablic. Kolejne wierszy opisuje poszczególne wiersze danej tablicy. Każdy z nich składa się z ciągu liczb całkowitych ().
Dodatkowo, w testach wartych łącznie punktów, .
Dla danych wejściowych:
4 5 2 6 -10 0 3 -6 -8 8 1 -5 3 -7 -3 2 4 -4 2 0 -1 3 -3
poprawną odpowiedzią jest:
17
Zadanie zapożyczone z CPSPC 2010.