Bicolored Horses#3248
Every day, farmer Ion (this is a Romanian name) takes out all his horses so they can run and play. When they are done, farmer Ion needs to take all the horses back to the stables. In order to do this, he places them in a straight line, and they follow him to the stables. Because the horses are very tired, farmer Ion decides that he does not want them to move more than necessary. So he develops the following algorithm: he places the first P_1 horses in the first stable, the next P_2 horses in the second stable, and so on. Moreover, he does not want any of his stables to be empty, and no horse is to be left outside.
You should also know that farmer Ion has only black or white horses, which do not get along very well. If there are black horses and white horses in one stable, then the coefficient of unhappiness for that stable is i \times j. The total coefficient of unhappiness is the sum of the coefficients in each of the stables.
Determine a way to place the horses into the stables so that the total coefficient of unhappiness is minimized.
The first line contains two numbers: (1 \le N \le 500) and (1 \le K \le N). The next lines each contain one number. The -th of these lines contains the color of the -th horse in the sequence: means the horse is black, means the horse is white.
Output a single number, the minimum possible value of the total coefficient of unhappiness.
مثال 1