Sesja

Rozważmy piramidę zbudowaną z ułożonych klocków z liczbami zbudowanej w ten sposób, iż liczby są układane warstwami. Każda liczba warstwy górnej ma pod sobą dwie liczby warstwy dolnej. Problem polega na znalezieniu maksymalnej sumy liczb poruszając się tylko po przyległych blokach od samej góry do dołu w jednym z dwóch kierunków pokazanych na rysunku strzałkami.

Na powyższym rysunku widzimy, że największą sumę równą 30 uzyskamy idąc po ścieżce: 7 -> 3 -> 8 -> 12.

Wejście:

W pierwszym wierszu dostajemy liczbę całkowitą dodatnią n < 1000 oznaczającą wysokość piramidy zakończoną znakiem nowej linii. W kolejnych wierszach podajemy liczby ułożone na piramidzie, rozdzielone spacją,zaczynając od góry. Poszczególne wiersze rozdzielone są znakiem nowej linii.

Wyjście:

Liczba całkowita oznaczająca maksymalną sumę ścieżki.

Przykład (patrz rys.)
Wejście:
4
7
3 8
8 1 0
7 12 10 10
Wyjście:
30

Wskazówka:
1. 
Tablicę dwuwymiarową w Pythonie tworzymy robiąc listę list:
t = []
for i in range(n):
   t.append(input().split(" "))
2. 
Zastosować algorytm dynamiczny.