P5425 [USACO19OPEN] I Would Walk 500 Miles G

Farmer John wants to divide his $N$ cows numbered $1 \ldots N$ ($N \leq 7500$) into $K$ non-empty groups ($2 \leq K \leq N$), such that any two cows from different groups must walk some distance to meet each other. Cows $x$ and $y$ (where $1 \leq x

The input consists of a single line containing $N$ and $K$, separated by a space.

Output the optimal value of $M$.

In this example, cow $1$ and cow $2$ are willing to walk $2019201817$ miles to meet. Cow $2$ and cow $3$ are willing to walk $2019201685$ miles. Cow $1$ and cow $3$ are willing to walk $2019201769$ miles. Therefore, if cow $1$ is put alone in one group, and cows $2$ and $3$ are put into another group, then $M = \min(2019201817, 2019201769) = 2019201769$ (this is the best result we can achieve in this problem). Translated by ChatGPT 5