Cut and Reorder

题目描述

给出两个长度为 $N$ 的序列：$A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。 你可以对序列 $A$ 任意次数按任意顺序执行以下两种操作。

在任意位置拆分 $A$ 并自由重排拆分得到的各段。每个拆分位置会产生代价 $C$。 更形式地，在代价为 $(X-1)C$ 的情况下，取长度为 $X+1$ 的下标序列 $(i_0,i_1,i_2,\ldots,i_X)\ (0=i_0\lt i_1\lt i_2\lt\cdots\lt i_X=N)$ 以及 $(1,2,\ldots,X)$ 的一个置换 $p$，并用按 $j$ 升序连接的各段 $(A_{i_{p_j-1}+1},A_{i_{p_j-1}+2},\ldots,A_{i_{p_j}})$ 的串联来替换 $A$。 选择一个整数 $k$ 和 $A$ 的任意一个元素，将该元素的值加上 $k$，代价为 $|k|$。

通过执行这些操作使 $A$ 和 $B$ 相等，求最小总代价。

输入格式

输入按下列格式从标准输入给出： $N$ $C$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

输出答案。

5 1
3 1 4 1 5
9 2 6 5 3

12

5 1000000000
3 1 4 1 5
9 2 6 5 3

15

22 467772225675200
814424018890229 837987908732596 281175505732576 405797525366223 319378664987871 305374284356649 519144936694626 316916938328237 590332737480143 506785561790072 945769796193819 365498597798550 5386616044591 672368930784037 478017750715806 340276460237787 176509793332130 2734777402752 677509027289850 250325127275409 260270543315523 103584313625431
720386673780641 77160494100361 540947273460639 255177791002759 969333325196025 477751866935037 369600749728569 466236682780196 343161112138696 541310338013515 42740499599240 165778332156355 618106559852784 16582487395877 591851763813728 221861304303645 982850624742022 728669467505250 337968530842725 746724490610504 61587851254728 451153536869240

4370668608634071

提示

$1\leq N\leq22$ $1\leq C\leq10^{15}$ $1\leq A_i\leq10^{15}\ (1\leq i\leq N)$ $1\leq B_i\leq10^{15}\ (1\leq i\leq N)$ 所有输入值都是整数。例如，可以通过执行以下操作使 $A$ 和 $B$ 相等。

对 $A_2$ 加 $2$。代价为 $2$，此时 $A$ 变为 $(3,3,4,1,5)$。 对 $A_4$ 加 $1$。代价为 $1$，此时 $A$ 变为 $(3,3,4,2,5)$。 对 $A_3$ 加 $3$。代价为 $3$，此时 $A$ 变为 $(3,3,7,2,5)$。 将 $A$ 拆分为 $(3,3)$ 和 $(7,2,5)$，并交换它们的顺序。代价为 $1$，此时 $A$ 变为 $(7,2,5,3,3)$。 对 $A_3$ 加 $1$。代价为 $1$，此时 $A$ 变为 $(7,2,6,3,3)$。 对 $A_4$ 加 $2$。代价为 $2$，此时 $A$ 变为 $(7,2,6,5,3)$。 对 $A_1$ 加 $2$。代价为 $2$，此时 $A$ 变为 $(9,2,6,5,3)$。

总代价为 $2+1+3+1+1+2+2=12$。 不可能以不超过 $11$ 的总代价使 $A$ 和 $B$ 相等，所以输出 $12$。
例如，可以通过执行以下操作使 $A$ 和 $B$ 相等。

对 $A_1$ 加 $6$。代价为 $6$，此时 $A$ 变为 $(9,1,4,1,5)$。 对 $A_2$ 加 $1$。代价为 $1$，此时 $A$ 变为 $(9,2,4,1,5)$。 对 $A_3$ 加 $2$。代价为 $2$，此时 $A$ 变为 $(9,2,6,1,5)$。 对 $A_4$ 加 $4$。代价为 $4$，此时 $A$ 变为 $(9,2,6,5,5)$。 对 $A_5$ 加 $-2$。代价为 $2$，此时 $A$ 变为 $(9,2,6,5,3)$。

总代价为 $15$。 不可能以不超过 $14$ 的总代价使 $A$ 和 $B$ 相等，所以输出 $15$。
注意输入和答案可能无法放入 $32\operatorname{bit}$ 整数。

标签: AtCoder|abc328G

来源

AtCoder|abc328G