Задача №115398. Сочи Парк
В Сочи Парке открылся новый аттракцион. Вдоль прямой расположены \(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.
| Доп. ограничения | ||||||
| Подзадача | Баллы | \(n\) | \(x_{0}\) | \(m\) | дополнительно | Необх. подзадачи |
| 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\) | 4 |
| 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}\) | У, 6 |
| 8 | 6 | – | \(x_{0} = 0\) | \(m \leq 10\,000\) | \(x_{i} \leq 10^{6}\) | 4, 6 |
| 9 | 10 | – | \(x_{0} \leq 10^{6}\) | \(m \leq 10\,000\) | \(x_{i} \leq 10^{6}\) | У, 4–8 |
| 10 | 7 | – | \(x_{0} \leq 10^{6}\) | \(m \leq 10^{5}\) | \(x_{i} \leq 10^{6}\) | У, 4–9 |
| 11 | 2 | – | – | \(m \leq 10\) | – | У, 1, 6, 7 |
| 12 | 12 | – | \(x_{0} = 0\) | \(m \leq 10^{5}\) | \(d = 1\) | – |
| 13 | 5 | – | – | \(m \leq 10^{5}\) | \(d = 1\) | 12 |
| 14 | 8 | – | \(x_{0} = 0\) | \(m \leq 10^{5}\) | – | 4, 6, 8, 12 |
| 15 | 2 | – | – | \(m \leq 10^{5}\) | – | У, 1–14 |
| 16 | 1 | – | – | \(m \leq 2 \cdot 10^{5}\) | – | У, 1–15 |
| 17 | 3 | – | – | \(m \leq 3 \cdot 10^{5}\) | – | У, 1–16 |
| 18 | 9 | – | – | – | – | У, 1–17 |
В первом тесте для второго участника (\(t_2=1\)) оптимальным будет следующий алгоритм поражения целей:
- Переместиться из точки \(x_0=2\) в точку \(x_0-d=-1\), потратив \(t_2=1\) калорию. Обратите внимание, координата посетителя может быть отрицательной.
- Поразить цель в точке \(x_2=0\), потратив \((-1 - 0)^2 = 1\) калорию.
- Переместиться в точку \(-1+2d=5\), потратив \(2t_2 = 2\) калории.
- Поразить цель в точке \(x_1=4\), потратив \((5 - 4)^2 = 1\) калорию.
- Переместиться в точку \(5+d=8\), потратив \(t_2=1\) калорию.
- Поразить цель в точке \(x_3=7\), потратив \((8 - 7)^2 = 1\) калорию.
Суммарные затраты энергии равны \(1 + 2 + 1 + 1 + 1 + 1 = 7\) калорий. Можно показать, что это минимальное количество энергии.
Для шестого участника (\(t_6=23\)) оптимальным будет следующий алгоритм поражения целей:
- Поразить цель в точке \(x_2=0\), потратив \((2 - 0)^2 = 4\) калории.
- Переместиться в точку \(2+d=5\), потратив \(t_6=23\) калории.
- Поразить цель в точке \(x_3=7\), потратив \((7 - 5)^2 = 4\) калории.
- Поразить цель в точке \(x_1=4\), потратив \((5 - 4)^2 = 1\) калорию.
Суммарные затраты энергии равны \(4 + 23 + 4 + 1 = 32\) калории. Можно показать, что это минимальное количество энергии.
3 4 0 7 2 3 7 0 1 2 3 4 23 25
3 7 10 12 13 32 33
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