P1792 [CTT] Planting Trees

In City A, there is a huge circular plaza. To green the environment and purify the air, the municipal government![]() decided to plant a ring of trees along the outer edge of the circular plaza. After receiving the order, the parks department initially planned $n$ planting positions, numbered clockwise from $1$ to $n$. Each position has an aesthetic value $A_i$, and if a tree is planted there, you gain this $A_i$ value. However, due to poor soil fertility in City A, two trees must not be planted at adjacent positions (positions $i$ and $i+1$ are adjacent; note that positions $1$ and $n$ are also adjacent). Finally, the municipal government![]()![]() provided the parks department with $m$ saplings and requires that all of them be planted. Please design a planting plan to maximize the total aesthetic value. If it is impossible to plant all $m$ saplings, output that there is no solution.

The first line contains two positive integers $n, m$. The second line contains $n$ integers, where the $i$-th integer represents $A_i$.

Output one integer, the maximum total aesthetic value achievable by the optimal planting plan. If there is no solution, output `Error!`.

testdata ID | $n$ size | testdata ID | $n$ size -|-|-|- $1$ | $30$ | $11$ | $200$ $2$ | $35$ | $12$ | $2007$ $3$ | $40$ | $13$ | $2008$ $4$ | $45$ | $14$ | $2009$ $5$ | $50$ | $15$ | $2010$ $6$ | $55$ | $16$ | $2011$ $7$ | $60$ | $17$ | $2012$ $8$ | $65$ | $18$ | $199999$ $9$ | $200$ | $19$ | $199999$ $10$ | $200$ | $20$ | $200000$ For all testdata: $m \le n$, $-1000 \le A_i \le 1000$. Translated by ChatGPT 5