P1484 Planting Trees

cyrcyr is planting trees today. He dug $n$ pits on a straight line. Each of these $n$ pits can be used to plant a tree, but to ensure every tree has sufficient nutrients, cyrcyr will not plant trees in two adjacent pits. Also, because cyrcyr does not have enough saplings, he will plant at most $k$ trees. Assuming cyrcyr has a special ability to foresee the profit from planting a tree in any pit (which may be negative), please help him compute his maximum total profit.

The first line contains two positive integers $n, k$. The second line contains $n$ integers. The $i$-th number denotes the profit from planting a tree in the $i$-th pit from left to right on the line.

Output a single number, the maximum profit that cyrcyr can obtain.

For $20\%$ of the testdata, $n \leq 20$. For $50\%$ of the testdata, $n \leq 6000$. For $100\%$ of the testdata, $1 \le n \le 300000$, $1 \le k \le \dfrac{n}{2}$, and the absolute value of the profit at any single position is at most $10^6$. Translated by ChatGPT 5