P7959 [COCI 2014/2015 #6] WTF

你有一个长度为 $n$ 的数组 $\textbf A$，一个值域为 $[1,n-1]$ 的长度为 $n+1$ 的数组 $\textbf{ID}$ 和一个整数 $r$。 我们通过以下伪代码对数组 $\textbf A$ 进行 Warshall-Turing-Fourier 变换 $^\textsf{[1]}$： ```cpp sum = 0 for i = 1 to n index = min{ID[i], ID[i+1]} sum = sum + A[index] Rorate(A, r) Change(A) for i = 1 to n index = max{ID[i], ID[i+1]} index = index + 1 sum = sum + A[index] Rorate(A, r) ``` 其中： - $\texttt{Change}(\textbf A)$ 表示把数组 $\textbf A$ 中所有元素分别改成它们的相反数。 - $\texttt{Rorate}(\textbf A,r)$ 表示把数组 $\textbf A$ 复制两遍得到数组 $\textbf B$，取 $\textbf B[n-r+1,2n-r]$ 代替数组 $\textbf A$。\ 即**向右旋转** $R$ 个位置。 你已经知道数组 $\textbf A$ 和整数 $r$，但你并不知道数组 $\textbf{ID}$。 你需要求出 WTF 变换后伪代码中 $\text{sum}$ 可能的最大值。 $\textsf{[1]}$：实际上并不存在，当然也可以叫做「Sept 变换」。

第一行两个整数 $n,r$。 接下来一行 $n$ 个整数，表示数组 $\textbf A$。

第一行一个整数，即伪代码中 $\text{sum}$ 可能的最大值。 第二行 $n+1$ 个整数，即使得 $\text{sum}$ 值最大的 $\textbf{ID}$ 数组。 **如果存在多组解，输出任意一种。**

#### 判分方式 如果输出只有第一行正确，可以得到 $50\%$ 的分数。 **但你必须保证第二行有 $\bm{n+1}$ 个符合要求的数。** #### 数据规模与约定 **本题采用 Special Judge。** - 对于 $20\%$ 的数据，有 $n\le 7$。 - 对于 $60\%$ 的数据，有 $n\le 300$。 - 对于 $100\%$ 的数据，有 $2\le n\le 3\times 10^3$，$1\le r\le n$，$\textbf A[i]\in[-10^4,10^4]$。 你需要保证你构造的 $\textbf{ID}[i]\in[1,n-1]$。 #### 说明 按原题配置，满分 160 分。 译自 **[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/)** [Contest #6](https://hsin.hr/coci/archive/2014_2015/contest6_tasks.pdf) Task F _**WTF**_。