P8963 "WHOI-4" Addition and Subtraction Construction

Little W gives you an **integer** array $x$ of length $n$. You need to construct an **integer** array $y$ of length $n$, and satisfy: 1. $\forall 1\le i,j,i+j\le n,y_{i+j}=y_i+y_j+k$, where $k$ is an integer that you must choose. 2. Minimize $d(x,y)=\sum\limits_{i=1}^n|x_i-y_i|$. 3. $-V\le y_i\le V$, where $V$ is a number given in the input.

The first line contains two integers $n,V$. The next line contains $n$ integers; the $i$-th integer represents $x_i$.

The first line contains two integers $k,d$, representing the value you choose and your answer. The next line contains $n$ integers; the $i$-th integer represents $y_i$. It is guaranteed that the minimum value of $d$ fits in `long long`.

**Constraints** - Subtask 1 ($20$ pts): $n\le10$, $V\le10$, $|x_i|\le10$. - Subtask 2 ($20$ pts): $n\le100$, $|x_i|\le100$, $V\le1000$. - Subtask 3 ($20$ pts): $n\le10^6$, $|x_i|\le10^6$, $V=10^{12}$. - Subtask 4 ($20$ pts): $n\le10^7$, $|x_i|\le10^7$, $V\le10^7$. - Subtask 5 ($20$ pts): $n\le10^7$, $|x_i|\le10^7$, $V\le 10^{12}$. For all testdata, it is guaranteed that $1\le n\le 10^7$, $|x_i|\le10^7$, $1\le V\le10^{12}$. **Notes about the Special Judge** For each test point: If your output format is incorrect, you will get $0$ points. If any number you output is not in the range $[-V,V]$, you will get $0$ points. If your sequence $y$ does not match the $k$ you output, you will get $0$ points. If your sequence $y$ does not match the $d$ you output, you will get $0$ points. Otherwise, the score you get for this test point is $\max\{0,\min\{100,10100-\frac{10000d}{d'}\}\}$ percent of the total score for this test point, where $d'$ is the $d$ value of the best answer. Translated by ChatGPT 5