Autor: Karol Kurach, program wzorcowy: Kamil Anikiej
Michał i Radek to koledzy ze szkoły. Obaj bardzo interesują się fizyką i odnoszą sukcesy w Olimpiadzie Fizycznej. Z okazji ostatnich wygranych zawodów, pani Elżbieta nagrodziła ich ogromnym, własnoręcznie wykonanym tortem.
Tort ma kształt prostokąta o wymiarach n x m i składa się z n * m kwadratowych segmentów. Koledzy mają zamiar podzielić go na 2 części. Niestety, tort nie jest taki sam w każdym miejscu. Każdemu segmentowi S(n,m) przypisana jest pewna liczba całkowita określająca jego smakowitość. Fizycy od razu odrzucili .prostacką. wg nich metodę podziału toru na pół i wylosowania kto dostanie lepszy kawałek. Zamiast tego postanowili zagrać w swojego rodzaju grę i podzielić tort zachowując przy tym poniższe reguły:
Grę zaczyna Radek, do niego należą segmenty na lewo od linii cięcia, do Michała na prawo od linii cięcia. Wygrywa oczywiście ten, u którego suma smakowitości wszystkich segmentów jest większa.
Jak to w życiu bywa , nie wszystkie strony pojedynku przestrzegają zasad fair-play. Michał, wieloletni prenumerator .Wróżki. potrafi przewidywać wyniki swych posunięć i zawsze gra perfekcyjnie. Wyrównaj szanse ! Pomóż Radkowi zjeść najbardziej smakowity kąsek zakładając , że jego przeciwnik gra bezbłędnie.
Napisz program, który:
Pierwszy wiersz zawiera dwie liczby całkowite n, m , 1 <= n , m <= 2000 oddzielone pojedynczym odstępem. Liczba n oznacza szerokość tortu, m . jego długość.
Kolejne n wierszy zawiera po m liczb całkowitych z przedziału <- 100000, 100000 > pooddzielanych pojedynczymi odstępami ; j-ta liczba w (i+1)-szym wierszu oznacza smakowitość segmentu (n- i+1 , j ) . [ (1,1)- lewy dolny segment ; (n,m) . prawy górny segment ] W kartezjańskim układzie współrzędnych, segment (1,1) oznacza po prostu kwadrat otoczony punktami (0,0), (0,1), (1,0), (1,1) , a segment (n,m) kwadrat otoczony punktami (m-1,n-1), (m-1,n) , (m,n-1) , (m,n).
W pierwszym i jedynym wierszu wyjścia powinna znajdować się liczba całkowita określająca największą smakowitość, jaką Radek może uzyskać dla swojej części tortu.
Dla danych wejściowych:
3 4 1 1 1 1 1 2 1 1 1 1 1 1
Poprawnym wynikiem jest:
7
Komentarz:
Podział tortu wygląda następująco ( segmenty R . własność Radka , M . Michała )
RRRM RRMM RMMM
( w tym wypadku Radek kroił cały czas w prawo a Michał w górę, czerwone .R. oznacza segment (1,1) )
Limit pamięci : 8 MB
[Zgłoś rozwiązanie] [Moje zgłoszenia]