A15048. Ice Cream Shop
编程题
普及/提高-
知识点
题目描述
On a beach there are $n$ huts in a perfect line, hut $1$ being at the left and hut $i+1$ being $100$ meters to the right of hut $i$ , for all $1 \le i \le n - 1$ . In hut $i$ there are $p_i$ people.
There are $m$ ice cream sellers, also aligned in a perfect line with all the huts. The $i$ -th ice cream seller has their shop $x_i$ meters to the right of the first hut. All ice cream shops are at distinct locations, but they may be at the same location as a hut.
You want to open a new ice cream shop and you wonder what the best location for your shop is. You can place your ice cream shop anywhere on the beach (not necessarily at an integer distance from the first hut) as long as it is aligned with the huts and the other ice cream shops, even if there is already another ice cream shop or a hut at that location. You know that people would come to your shop only if it is strictly closer to their hut than any other ice cream shop.
If every person living in the huts wants to buy exactly one ice cream, what is the maximum number of ice creams that you can sell if you place the shop optimally?
There are $m$ ice cream sellers, also aligned in a perfect line with all the huts. The $i$ -th ice cream seller has their shop $x_i$ meters to the right of the first hut. All ice cream shops are at distinct locations, but they may be at the same location as a hut.
You want to open a new ice cream shop and you wonder what the best location for your shop is. You can place your ice cream shop anywhere on the beach (not necessarily at an integer distance from the first hut) as long as it is aligned with the huts and the other ice cream shops, even if there is already another ice cream shop or a hut at that location. You know that people would come to your shop only if it is strictly closer to their hut than any other ice cream shop.
If every person living in the huts wants to buy exactly one ice cream, what is the maximum number of ice creams that you can sell if you place the shop optimally?
输入格式
The first line contains two integers $n$ and $m$ ( $2 \le n \le 200\,000$ , $1 \le m \le 200\,000$ ) — the number of huts and the number of ice cream sellers.
The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ( $1 \le p_i \le 10^9$ ) — the number of people in each hut.
The third line contains $m$ integers $x_1, x_2, \ldots, x_m$ ( $0 \le x_i \le 10^9$ , $x_i \ne x_j$ for $i \ne j$ ) — the location of each ice cream shop.
The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ( $1 \le p_i \le 10^9$ ) — the number of people in each hut.
The third line contains $m$ integers $x_1, x_2, \ldots, x_m$ ( $0 \le x_i \le 10^9$ , $x_i \ne x_j$ for $i \ne j$ ) — the location of each ice cream shop.
输出格式
Print the maximum number of ice creams that can be sold by choosing optimally the location of the new shop.
输入输出样例
输入 #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
说明/提示
In the first sample, you can place the shop (coloured orange in the picture below) $150$ meters to the right of the first hut (for example) so that it is the closest shop to the first two huts, which have $2$ and $5$ people, for a total of $7$ sold ice creams.
In the second sample, you can place the shop $170$ meters to the right of the first hut (for example) so that it is the closest shop to the last two huts, which have $7$ and $8$ people, for a total of $15$ sold ice creams.
In the second sample, you can place the shop $170$ meters to the right of the first hut (for example) so that it is the closest shop to the last two huts, which have $7$ and $8$ people, for a total of $15$ sold ice creams.
