P2780 [AHOI2016 Junior] Game

Xiao Xue and Xiao Keke are playing a number game. They have prepared $n$ cards, each with an integer on it. At the beginning, Xiao Xue chooses an integer $t$ with $a \le t \le b$ and tells Xiao Keke the value of $t$. Then Xiao Keke selects exactly $k$ cards and sums their numbers; denote this sum by $m$. Xiao Xue wants the absolute difference between $t$ and $m$ to be as large as possible, while Xiao Keke wants it to be as small as possible. Before the game starts, both of them know $n$, $a$, $b$, and $k$, and also the number on every card. After Xiao Xue decides $t$, it cannot be changed, and only then does Xiao Keke select the cards. Xiao Xue wants to know, under optimal play by both of them, how large the absolute difference between $t$ and $m$ can be.

The input has two lines. The first line contains 4 integers $n$, $k$, $a$, and $b$, satisfying $1 \le k \le n \le 250$ and $0 \le a \le b \le 75000$. The second line contains $n$ integers, namely $x_1$ to $x_n$, which are the numbers on the cards. Each number $x_i$ satisfies $0 \le x_i \le 300$.

Output one line with a single integer, which is the maximum possible value of the absolute difference between $t$ and $m$.

For 30% of the testdata, $1 \le k \le n \le 20$ and $0 \le a \le b \le 6000$. For 80% of the testdata, $1 \le k \le n \le 65$ and $0 \le a \le b \le 19650$. For 100% of the testdata, $1 \le k \le n \le 250$ and $0 \le a \le b \le 75000$. Translated by ChatGPT 5