P1216 [IOI 1994 / USACO1.5] Number Triangles

Look at the number pyramid below. Write a program to find a path from the top to any position on the bottom that yields the maximum possible sum of the numbers along the path. At each step, you may move to the left-down or right-down adjacent position.  In the sample above, the path $7 \to 3 \to 8 \to 7 \to 5$ produces the maximum sum.

The first line contains a single integer $r$, the number of rows. Each of the next $r$ lines describes one row of the number triangle: for each $i$ from $1$ to $r$, the $i$-th line contains $i$ integers.

Output a single line containing the maximum possible sum.

Constraints For $100\%$ of the testdata, $1 \le r \le 1000$, and all input integers are in the range $[0, 100]$. Problem translation from NOCOW. IOI 1994 Day 1 T1 / USACO Training Section 1.5. Translated by ChatGPT 5