| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 35 | 3 | 3 | 8.571% |
В Сочи Парке открылся новый аттракцион. Вдоль прямой расположены $n$ целей, координата $i$-й цели равна $x_i$ ($1\le i\le n$). Посетители должны поразить все эти цели в произвольном порядке. Для поражения целей используются мячики. Если посетитель находится в точке с координатой $x$ и хочет поразить цель, находящуюся в точке $x_i$, ему потребуется потратить $(x-x_i)^2$ калорий.
Посетитель входит в аттракцион в точке с координатой $x_0$. Неограниченные запасы мячиков находятся в точке входа, а также во всех точках на расстоянии $d$ друг от друга, то есть в точках $x_0+kd$, где $k$ --- произвольное целое число. Переносить мячики запрещено правилами аттракциона, поэтому бросать их можно только из этих точек.
В день между турами $m$ участников олимпиады посетят Сочи Парк. Участники соревнования находятся в разной физической форме, поэтому $j$-му участнику олимпиады для перемещения на расстояние $d$ требуется $t_j$ калорий.
Вам нужно определить, какое минимальное число калорий необходимо каждому участнику для поражения всех целей аттракциона.
В первой строке задано одно целое число $n$ ($1 \leq n \leq 3 \cdot 10^{5}$) --- количество целей в аттракционе.
Во второй строке заданы $n$ целых чисел $x_{1}, x_{2}, \ldots, x_{n}$ ($0 \leq x_{i} \leq 10^{9}$) --- координаты целей.
В третьей строке заданы два целых числа $x_{0}$ и $d$ ($0 \leq x_{0} \leq 10^{9}$, $1 \leq d \leq 2 \cdot 10^{6}$) --- точка входа посетителя аттракциона и расстояние между местами нахождения запасов мячиков.
В четвертой строке задано одно целое число $m$ ($1 \leq m \leq 6 \cdot 10^{5}$) --- количество участников олимпиады.
В следующих $m$ строках содержится по одному целому числу $t_j$ ($0 \leq t_j \leq 10^{8}$) --- количество энергии, необходимое $j$-му участнику олимпиады для перемещения между двумя соседними местами нахождения запасов мячиков.
Для каждого участника олимпиады выведите одно целое число --- минимальное количество, необходимое ему для перемещения и поражения всех целей.
При данных ограничениях ответ не превосходит максимального значения 64-битного знакового типа данных. Однако для промежуточных вычислений может понадобиться тип данных __int128 в C++ (поддерживается только в компиляторе GNU C++), BigInteger в Java, int в Python.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $m = 1$, $t_{1} = 0$ |
| 2 | 7 | $n = 1$, $m \leq 10\,000$ |
| 3 | 8 | $n = 2$, $m \leq 10\,000$, $x_{1} \leq x_{0} \leq x_{2}$ |
| 4 | 3 | $n \leq 50$, $x_{0} = 0$, $m \leq 50$, $d \leq 50$, $x_{i} \leq 50$ |
| 5 | 2 | $n \leq 50$, $x_{0} \leq 50$, $m \leq 50$, $d \leq 50$, $x_{i} \leq 50$ |
| 6 | 4 | $x_{0} = 0$, $m \leq 10$, $x_{i} \leq 10^{6}$ |
| 7 | 2 | $x_{0} \leq 10^{6}$, $m \leq 10$, $x_{i} \leq 10^{6}$ |
| 8 | 6 | $x_{0} = 0$, $m \leq 10\,000$, $x_{i} \leq 10^{6}$ |
| 9 | 10 | $x_{0} \leq 10^{6}$, $m \leq 10\,000$, $x_{i} \leq 10^{6}$ |
| 10 | 7 | $x_{0} \leq 10^{6}$, $m \leq 10^{5}$, $x_{i} \leq 10^{6}$ |
| 11 | 2 | $m \leq 10$ |
| 12 | 12 | $x_{0} = 0$, $m \leq 10^{5}$, $d = 1$ |
| 13 | 5 | $m \leq 10^{5}$, $d = 1$ |
| 14 | 8 | $x_{0} = 0$, $m \leq 10^{5}$ |
| 15 | 2 | $m \leq 10^{5}$ |
| 16 | 1 | $m \leq 2 \cdot 10^{5}$ |
| 17 | 3 | $m \leq 3 \cdot 10^{5}$ |
| 18 | 9 |
3 4 0 7 2 3 7 0 1 2 3 4 23 25
3 7 10 12 13 32 3
4 30 239 57 179 0 7 5 1 10 15 100 100000
49 355 525 3378 93311
4 100 2 101 666 9 10 5 777 1 2 15 10
49597 91 159 1043 703
В первом тесте для второго участника ($t_2=1$) оптимальным будет следующий алгоритм поражения целей:
Суммарные затраты энергии равны $1 + 2 + 1 + 1 + 1 + 1 = 7$ калорий. Можно показать, что это минимальное количество энергии.
Для шестого участника ($t_6=23$) оптимальным будет следующий алгоритм поражения целей:
Суммарные затраты энергии равны $4 + 23 + 4 + 1 = 32$ калории. Можно показать, что это минимальное количество энергии.