Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Kojarzysz takie zadanie Kratka? Tak? No to powodzenia tym razem! Nie? Jakże mi przykro… Na szczęście możesz od razu zacząć od trudniejszego zadania.
Dana jest prostokąt wymiaru N × M wypełniony liczbami. Należy wybrać liczby o jak największej sumie, nie wolno jednak wybrać dwóch leżących w sąsiednich komórkach prostokąta. Dwie komórki prostokąta uznajemy za sąsiednie jeśli dzielą bok.
Napisz program, który: wczyta wymiary prostokąta oraz umieszczone w nim liczby, wyznaczy maksymalną możliwą sumę liczb, które można wybrać zgodnie z zasadami i wypisze wynik na wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, określające wysokość i szerokość prostokąta. W kolejnych N wierszach znajduje się po M liczb Ai, j. Są to liczby umieszczone w prostokącie.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć maksymalna suma liczb, które można wybrać zgodnie z regułami podanymi powyżej.
Ograniczenia
1 ≤ N, M ≤ 50, 0 ≤ Ai, j ≤ 1 000 000.
Przykład
| Input | Output | |
|
|