← 返回题目列表

Codeforces · 1662/I

I. 冰淇淋店

中文机器翻译题面 查看原题

在海滩上,有 $$$n$$$ 小屋排成完美的直线,小屋 $$$1$$$ 位于左侧,小屋 $$$i+1$$$ 位于小屋 $$$i$$$ 右侧 $$$100$$$ 米处,对于所有 $$$1 \le i \le n - 1$$$。小屋里$$$i$$$ 有$$$p_i$$$ 人。

这里有 $$$m$$$ 冰淇淋小贩,也与所有小屋排成一排。第 $$$i$$$ 个冰淇淋卖家的商店位于第一个小屋右侧 $$$x_i$$$ 米处。所有冰淇淋店都位于不同的位置,但它们可能与小屋位于同一位置。

您想开一家新冰淇淋店,并且想知道您的店的最佳位置在哪里。您可以将冰淇淋店放置在海滩上的任何位置(不一定距第一个小屋为整数距离),只要它与小屋和其他冰淇淋店对齐即可,即使该位置已经有另一家冰淇淋店或小屋。您知道,只有当您的店比任何其他冰淇淋店更靠近他们的小屋时,人们才会来您的店。

如果住在小屋里的每个人都想买一份冰淇淋,那么如果您对商店进行最佳布局,您最多可以出售多少冰淇淋?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — 小屋的数量和冰淇淋卖家的数量。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 10^9$$$) — 每个小屋中的人数。

第三行包含 $$$m$$$ 整数 $$$x_1, x_2, \ldots, x_m$$$ ($$$0 \le x_i \le 10^9$$$, $$$x_i \ne x_j$$$ for $$$i \ne j$$$) — 每个冰淇淋店的位置。

输出

打印通过选择新商店的最佳位置可以出售的冰淇淋的最大数量。

示例

输入 #1

3 1
2 5 6
169

输出 #1

7

输入 #2

4 2
1 2 7 8
35 157

输出 #2

15

输入 #3

4 1
272203905 348354708 848256926 939404176
20

输出 #3

2136015810

输入#4

3 2
1 1 1
300 99

输出#4

2

注意

在第一个示例中,您可以将商店(下图中的橙色)$$$150$$$ 米放置在第一个小屋的右侧(例如),这样它就是距离前两个小屋最近的商店,前两个小屋有 $$$2$$$ 和 $$$5$$$ 人,总共售出 $$$7$$$ 冰淇淋。

在第二个示例中,您可以将商店 $$$170$$$ 米放置在第一个小屋的右侧(例如),以便它是距离最后两个小屋最近的商店,最后两个小屋有 $$$7$$$ 和 $$$8$$$ 人,总共售出 $$$15$$$ 冰淇淋。