P5336 [THUSC 2016] Report Cards

The final exams are over. Head teacher Mr. L needs to hand out the report cards to every student. Mr. L has $n$ report cards, stacked on the desk in order from $1$ to $n$, where the score on report card $i$ is $W_i$. The report cards are handed out in batches. When handing them out, Mr. L will take a consecutive segment from the current stack of report cards, and the students in that segment come to pick up their own report cards. After this batch of students finishes, Mr. L then takes another consecutive segment from the remaining report cards for the next batch. After several batches, all report cards will be handed out. However, handing out report cards is a headache. On one hand, he needs to take care of the students' feelings, so students with scores that differ too much should not pick up their report cards in the same batch. On the other hand, he must consider the time cost and try to reduce the number of batches. For a distribution plan, we define its cost as: $$a \times k + b \times \sum_{i = 1} ^ k (max_i - min_i) ^ 2$$ where $k$ is the number of batches. For the report cards handed out in the $i$-th batch, $max_i$ is the highest score and $min_i$ is the lowest score. $a$ and $b$ are given evaluation parameters. Now, please help Mr. L find the plan with the minimum cost, and report this minimum cost to Mr. L. Of course, the number of batches $k$ is up to you.

The first line contains a positive integer $n$, indicating the number of report cards. The second line contains two non-negative integers $a, b$, indicating the given evaluation parameters. The third line contains $n$ positive integers $w_i$, where $w_i$ is the score on the $i$-th report card.

Output a single positive integer, indicating the minimum cost.

Constraints: $n \leq 50$，$a \leq 1500$，$b \leq 10$，$w_i \leq 1000$。 Translated by ChatGPT 5