E. [R15E]扫地机器人

    Type: Default 2000ms 512MiB

[R15E]扫地机器人

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/512M

题目描述

数轴上有 nn 个扫地机器人和 mm 个垃圾,ii 号机器人的初始坐标为 aia_i,第 ii 个垃圾的坐标为 bib_i

扫地机器人每秒的移动距离为 11,分为三个种类:

  • 11 类机器人只能向左移动,也就是说如果现在有一个 11 类机器人位于坐标 xx,那么 11 秒后它位于坐标 x1x-1
  • 22 类机器人只能向右移动,也就是说如果现在有一个 22 类机器人位于坐标 xx,那么 11 秒后它位于坐标 x+1x+1
  • 33 类机器人可以自己选择向左或向右移动,随时可以改变方向且改变方向不花时间,也就是说如果现在有一个 33 类机器人位于坐标 xx,那么 11 秒后它可能位于坐标 x1x-1 或坐标 x+1x+1

一个垃圾被任意一个扫地机器人经过时会被清理,清理垃圾不花时间。多个扫地机器人可以同时位于一个坐标。

求清理所有垃圾最少需要花多少秒。数据保证至少有一个 33 类机器人。

格式

输入格式

第一行包含两个整数 n,mn,m,分别表示扫地机器人的数量和垃圾的数量。

第二行包含 nn 个整数 aia_i,分别表示每个扫地机器人的初始坐标。

第三行包含 nn 个整数 kik_i,分别表示每个扫地机器人的类型。

第四行包含 mm 个整数 bib_i,分别表示每个垃圾的坐标。

输出格式

输出一个整数表示清理所有垃圾最少需要花多少秒。

样例

样例输入 #1

3 6
3 9 14
3 2 3
6 15 1 9 8 4

样例输出 #1

7

样例解释 #1

其中一种方案为:

  • 11 号机器人 020\sim 2 秒向左移动到达坐标 11272\sim 7 秒向右移动到达坐标 66,过程中可以清理到垃圾:1,3,61,3,6
  • 22 号机器人 070\sim 7 秒向右移动到达坐标 1515,过程中可以清理到垃圾:2,42,4
  • 33 号机器人 070\sim 7 秒向左移动到达坐标 77,过程中可以清理到垃圾:4,54,5

所有的垃圾都在 77 秒内被清理了。

样例输入 #2

1 2
500000000
3
1000000000 1

样例输出 #2

1499999998

数据规模

对于 20%20\% 的数据,n1000n\leq 1000m2000m\leq 2000k1=3k_1=3,且对于 i>1i>11ki21\leq k_i\leq 2

对于 40%40\% 的数据,k1=3k_1=3,且对于 i>1i>11ki21\leq k_i\leq 2

另有 20%20\% 的数据,ki=3k_i=3

对于 100%100\% 的数据,1n1051\leq n\leq 10^51m2×1051\leq m\leq 2\times 10^51ai,bi10181\leq a_i,b_i\leq 10^{18}1ki31\leq k_i\leq 3。数据保证至少有一个 ii 满足 ki=3k_i=3

代码源挑战赛 Round 15

Not Attended
Status
Done
Rule
DMY
Problem
6
Start at
2025-6-6 20:00
End at
2025-6-6 21:30
Duration
1.5 hour(s)
Host
Partic.
579