Čokolade
레이팅 미적용의견: 0
Little Lana and little Fran are visiting a chocolate factory. They have seen how
chocolate is made, tasted many chocolates, and now they want to buy some of the
chocolates.
In the shop, there are \(n\) different chocolates, and the \(i-th\) of them has the price
\(c@@RISE_MATH_BLOCK_0@@i - k\)
kunas.
Let’s denote \(l\) as the amount Lana has to pay, and \(f\) as the amount Fran has to pay. Lana, dissatisfied
with Fran’s deal, wants to spite Fran and choose the chocolates so the value of the expression \(l - f\) is as
small as possible. Since Fran is hesitant and doesn’t know how many he wants to buy, Lana wants to
know the minimal value of the expression \(l - f\) for \(q\) different numbers \(k@@RISE_MATH_BLOCK_1@@i\).
Help her choose the chocolates and determine the minimum value of the expression \(l - f\) for each of the \(q\)
queries.
Subtask 1 (15 points): n, \(q \le 1000\), \(c\)\(i\), k\(i \le 10^{6}\)
Subtask 2 (20 points): \(k_{1}\) = . . . = \(k_{n}\)
Subtask 3 (35 points): No additional constraints.
The first line contains two integers \(n\) and \(q\) (\(1 \le n\), \(q \le 10^{5}\)), the number of chocolates, and the number of
queries.
The second line contains \(n\) integers \(c\)1, c2, . . . , c\(q\) (\(1 \le c@@RISE_MATH_BLOCK_0@@i\) and \(m@@RISE_MATH_BLOCK_1@@i \le 10^{9}\), \(1 \le m\)\(i \le n\)), Fran’s bound, and the
number of chocolates they are going to buy.
Print \(q\) lines. In the \(i-th\) line print the answer to Lana’s \(i-th\) query.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | n, \(q \le 1000\), \(c\)\(i\), k\(i \le 10^{6}\) |
2 | 20점 | \(k_{1}\) = . . . = \(k_{n}\) |
3 | 35점 | No additional constraints. |
5 2
1 9 22 10 19
18 4
5 234
-217 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 54
16
7
13 3
5 6 7
10 1
5 3
3 35
12
0Clarification of the first example:
In the first query, Lana can take chocolates with prices 1, 9, 22, and 10. Lana will pay 38 kunas, and Fran
4 kunas. The answer is 38 −4 = 34.
In the second query, Lana will choose chocolates with prices 22 and 19. She will pay 10 kunas, and Fran
will pay 31 kunas. The answer is 10 −31 = −21.
평가 및 의견
Čokolade
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Čokolade