P1544 Triple Experience

A number pyramid has $n$ rows of integers. The $i$-th row ($1 \le i \le n$) has $i$ numbers. One example is as follows. ```text 7 3 9 8 1 0 2 7 4 4 4 5 2 6 5 ``` Now you start at the top of the pyramid (the first row) and want to reach the bottom (the $n$-th row). At each step, you can move to the number down-left or down-right of your current position. Also, as a powerful kid, you may choose at most $k$ numbers in the pyramid and make them $3$ times their original value. You will collect all numbers along your path. Your final score is the sum of the collected numbers. Find the maximum possible score.

The first line contains two integers $n,k$, the number of rows in the number pyramid and the maximum count of numbers that can be multiplied by $3$. Then follow $n$ lines. The $i$-th of them contains $i$ space-separated integers, which are the numbers in the $i$-th row of the pyramid: $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$.

Output a single integer, the maximum score.

Constraints: For $30\%$ of the testdata, $k \le n \le 6$, and for any $1 \le i \le n$, $1 \le j \le i$ it holds that $0 \le a_{i,j} \le 100$. For $100\%$ of the testdata, $1 \le n \le 100$, $0 \le k \le \dfrac{n(n+1)}{2}$, and for any $1 \le i \le n$, $1 \le j \le i$ it holds that $|a_{i,j}| \le 10^9$. Translated by ChatGPT 5