P11114 [ROI 2024] 小推车 (Day 1)

翻译自 [ROI 2024 D1T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。

航空公司提供了一种新型的商务舱，飞机上的座位沿着过道排列。假设座位总数为 $n$，座位的坐标从 $1$ 到 $n$。 每个乘客都有一个饮料偏好，饮料的种类共有 $k$ 种，编号从 $1$ 到 $k$。每个乘客只能选择一种饮料。在飞机上，饮料需要从一辆小推车上分给乘客。 饮料装在一个瓶子里，每个瓶子的饮料可以服务 $p$ 个乘客。也就是说，一个瓶子的容量为 $p$。小推车最多可以装载 $m$ 个瓶子。保证 $k\le m$。 乘客按照座位号从 $1$ 到 $n$ 依次接受服务。小推车从座位前方的起点（坐标为 $0$）开始移动，并最终到达终点（坐标为 $n + 1$）。在小推车服务乘客的过程中，它可能需要去往储藏室中装载新的饮料。储藏室可能位于飞机前部的起点处，也可能位于后部的终点处，也有可能两侧都有。 如果小推车在座位 $i$ 的位置，它需要移动到起点处的储藏室的距离是 $i$，而到达终点处的储藏室的距离是 $n + 1 - i$。小推车在行进过程中可能需要补充饮料，如果小推车到达储藏室，它可以卸下空的瓶子，并装载新的饮料。不可以卸下还装有饮料的瓶子。在补充饮料后，小推车应该回到第一个未提供饮料的乘客的位置，再继续向后为乘客提供服务。 你需要计算小推车从 $0$ 移动到 $n + 1$ 的最小总移动距离，以便为所有乘客提供所需的饮料。

第一行包含四个整数 $n$，$m$，$k$ 和 $p$，分别表示座位数量、小推车所装瓶子的容量、饮料种类数量和每个瓶子所装饮料的容量。 第二行包含一个整数 $c$，表示储藏室的位置，$c$ 的取值范围是 $1$ 到 $3$。$c=1$ 表示储藏室只在终点位置；$c=2$ 表示储藏室只在起点位置；$c=3$ 表示储藏室在起点和终点都有。 第三行包含 $n$ 个整数 $a_i$，表示第 $i$ 个座位的乘客需要的饮料的类型。

输出一个整数，表示小推车在服务所有乘客的过程中所需的最小移动距离。

在第一个样例中，小推车可以装载 $m = 2$ 个瓶子，每瓶含 $p = 1$ 份饮料。储藏室位于客舱的尽头。 - 首先，小推车需要装上饮料 $1$ 和 $2$，这些饮料将分发给座位 $1$ 和 $2$ 的乘客，小推车需要行驶 $2$ 的距离从起点 $0$ 到点 $2$，即 $d_1=2$。 - 接着，小推车需要前往客舱尽头的储藏室（距离为 $4$），装上饮料 $1$ 和 $2$，然后返回到座位 $3$（小推车需要移动 $3$ 的距离）。$d_2=4+3=7$。 - 然后，小推车要为座位 $3$ 和 $4$ 的乘客提供饮料 $1$ 和 $2$（小推车在座位 $3$ 和 $4$ 之间移动 $1$ 的距离）。$d_3=1$。 - 最后，小推车需要再次前往储藏室（从座位 $4$ 到储藏室的距离为 $2$），装上饮料 $1$，从储藏室返回到座位 $5$（距离为 $1$），服务完该乘客后再移动 $1$ 的距离到客舱尽头。$d_4=2+1+1=4$。 总距离为 $d_1+d_2+d_3+d_4=2+7+1+4=14$。 在第二个样例中，小推车可以装载 $m = 3$ 个瓶子，每瓶含 $p = 2$ 份饮料。储藏室位于客舱的前端。小推车需要装满 $3$ 瓶饮料 $1$，服务座位 $1$ 到 $4$ 的乘客。之后，$2$ 瓶饮料 $1$ 将被用完，需要立刻前往储藏室装满 $2$ 瓶饮料 $2$，然后服务座位 $5$ 到 $8$ 的乘客（如果在服务完乘客 $5$ 后再回储藏室补充饮料，则要移动更长的距离）。 在第三个样例中，小推车可以装载 $m = 3$ 个瓶子，每瓶含 $p = 2$ 份饮料，储藏室分别位于客舱的两端。为了服务乘客，需要 $2$ 瓶饮料 $2$，以及饮料 $1$ 和 $3$ 各 $1$ 瓶，因此需要去储藏室更换空瓶。最好的方案是在服务完座位 $3$ 的乘客后，再去客舱前端的储藏室换取饮料 $2$。 在第四个样例中，小推车需要装载每种饮料各 $1$ 瓶，并且由于每瓶含 $2$ 份饮料，这样可以在不额外补充的情况下服务所有乘客。 在第五个样例中，需要进行两次补充，小推车在服务完乘客 $3$ 后需要第一次返回客舱开头的储藏室，第二次则是在服务完乘客 $6$ 后去到客舱尽头的储藏室。 原题目有十二个子任务，由于洛谷限制这里不能全部上传。 对于 $100\%$ 的数据，$3\le n\le 10^6,1\le p\le 10^6,1\le a_i\le k\le m\le 10^6,1\le c\le3$。