CF704B
有 nn 个元素,第 ii 个元素有五个参数 x_i, a_i, b_i, c_i, d_ixi,ai,bi,ci,di。
你需要求出一个 1 \sim n1∼n 的排列 pp,满足 p_1 = s, p_n = ep1=s,pn=e,同时最小化这个排列的权值。一个排列的权值定义为 \sum_{i = 1}^{n - 1} f(p_i, p_{i + 1})∑i=1n−1f(pi,pi+1),其中
- 若 i > ji>j,则 f(i, j) = x_i - x_j + c_i + b_jf(i,j)=xi−xj+ci+bj。
- 若 i < ji<j,则 f(i, j) = x_j - x_i + d_i + a_jf(i,j)=xj−xi+di+aj。
你只需要求出排列的最小权值即可。
数据范围:1 \leq n \leq 5 \times 10^31≤n≤5×103,s \neq es=e,1 \leq x_1 < x_2 < \dots < x_n \leq 10^91≤x1<x2<⋯<xn≤109,1 \leq a_i, b_i, c_i, d_i \leq 10^91≤ai,bi,ci,di≤109。
时空限制:44s / 250250MiB。