P2248 Segmentation

You are given $n$ numbers $a_1 \sim a_n$, and you need to partition them into several contiguous segments, with the constraint that there are $m$ specified pairs of numbers that cannot be placed in the same segment. The cost of creating one segment is: $$K + S \times (P - Q)$$ where $K$ and $S$ are given constants, $P$ is the maximum value in that segment, and $Q$ is the minimum value in that segment. You need to find a partitioning scheme that minimizes the sum of costs over all segments.

The first line contains two positive integers $n,m$. The second line contains two non-negative integers $K,S$. The third line contains $n$ non-negative integers $a_1 \sim a_n$. Each of the next $m$ lines contains $2$ positive integers $p_i,q_i$, indicating that $a_{p_i},a_{q_i}$ cannot be in the same segment.

Output a single line containing the minimum possible sum of the costs over all segments.

For $10\%$ of the testdata, $n \leq 10$. For $30\%$ of the testdata, $n \leq 1500$. For another $10\%$ of the testdata, $S = 0$. For another $30\%$ of the testdata, $m = 0$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le m \le 10^5$, $0 \le K,S,a_i \le 10^5$, $1 \le p_i,q_i \le n$, $p_i \ne q_i$. Translated by ChatGPT 5