P6898 [ICPC 2014 WF] Metal Processing Plant

Yulia works for a metal processing plant in Ekaterinburg. This plant processes ores mined in the Ural mountains, extracting precious metals such as chalcopyrite, platinum and gold from the ores. Every month the plant receives $n$ shipments of unprocessed ore. Yulia needs to partition these shipments into two groups based on their similarity. Then, each group is sent to one of two ore processing buildings of the plant. To perform this partitioning, Yulia first calculates a numeric distance $d(i, j)$ for each pair of shipments $1 \le i \le n$ and $1 \le j \le n$, where the smaller the distance, the more similar the shipments $i$ and $j$ are. For a subset $S \subseteq \{ 1, \ldots , n\} $ of shipments, she then defines the disparity $D$ of $S$ as the maximum distance between a pair of shipments in the subset, that is, $$ D(S) = \max _{i, j \in S} d(i, j). $$ Yulia then partitions the shipments into two subsets $A$ and $B$ in such a way that the sum of their disparities $D(A) + D(B)$ is minimized. Your task is to help her find this partitioning.

无

无

Time limit: 2000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2014