Problem Description

Xiao Lan wants to distribute $n$ packs of candies to $m$ children at his birthday party. Every pack must be given out, and each child must receive at least one pack, possibly more.

Xiao Lan has prepared the candies in advance. To make the distribution more even on the party day, he wants to compute a plan beforehand.

He numbers the candy packs from $1$ to $n$, and the $i$-th pack has weight $w_{i}$. The children are numbered from $1$ to $m$. Each child can only receive candies whose indices form a consecutive segment. Xiao Lan has thought for a long time but still cannot find a suitable plan so that every child gets roughly the same total weight. Therefore, he needs your help. To distribute better, he can buy some extra candies so that certain indexed packs have two copies. When a pack with some index has two copies, any single child can receive at most one of the two copies.

Find a plan that minimizes the difference between the maximum total weight and the minimum total weight among all children, and output this difference.

For example, Xiao Lan has 5 packs of candies with weights $6,1,2,7,9$. If he wants to distribute them to 2 children, he can buy an extra copy of every pack. Then both children can receive packs $1$ to $5$, and each gets total weight $25$, so the difference is $0$.

As another example, Xiao Lan has 5 packs of candies with weights $6,1,2,7,9$. If he wants to distribute them to 3 children, he can buy an extra copy of pack $3$. The first child receives packs $1$ to $3$, the second receives packs $3$ to $4$, and the third receives pack $5$. Each child gets total weight $9$, so the difference is $0$.

As another example, Xiao Lan has 5 packs of candies with weights $6,1,2,7,9$. If he wants to distribute them to 4 children, he can buy an extra copy of packs $3$ and $5$, and he still can make each child receive total weight $9$, so the difference is $0$.

As another example, Xiao Lan has 5 packs of candies with weights $6,1,2,7,9$. If he wants to distribute them to 5 children, he can buy an extra copy of packs $4$ and $5$. The first child receives packs $1$ to $2$ with total weight $7$, the second child receives packs $3$ to $4$ with total weight $9$, the third child receives pack $4$ with total weight $7$, and the fourth and fifth children both receive pack $5$ with total weight $9$. The difference is $2$.

Input Format

The first line contains two integers $n$ and $m$, representing the number of candy packs and the number of children.

The second line contains $n$ integers $w_{1}, w_{2}, \cdots, w_{n}$, representing the weight of each pack.

Output Format

Output one integer, representing the difference between the maximum total weight and the minimum total weight among the children in the optimal plan.

5 2
6 1 2 7 9

0

5 5
6 1 2 7 9

2

Hint

For $30\%$ of the testdata, $1 \leq n \leq 10, 1 \leq m \leq 10, 1 \leq w_{i} \leq 10$.

For $60\%$ of the testdata, $1 \leq n \leq 30, 1 \leq m \leq 20, 1 \leq w_{i} \leq 30$.

For all testdata, $1 \leq n \leq 100, 1 \leq m \leq 50, 1 \leq w_{i} \leq 100$. In the testdata, $w_{i}$ are generated randomly and uniformly within some interval.

Lanqiao Cup 2021, Round 1, Provincial Contest, Group A, Problem J.

Translated by ChatGPT 5