a103. P_5_6 線性函數(同Q-3-14，分治版)

Content

有N線性函數$f_i(x)=a_ix+b_i$，$1 \leq i \leq N$。定義$F(x) = \displaystyle\max_i f_i(x)$。輸入$c[i]$, $1 \leq i \leq m$，請計算$\displaystyle\sum^{m}_{i=1}F(c[i])=1$。

Input

第一行是N與m。接下來有N行，依序每行兩個整數ai與bi，最後一行有m個整數c[1], c[2], …, c[m]。每一行的相鄰數字間以空白隔開。N≤1e5，m≤5e4，輸入整數絕對值不超過1e7，答案不超過1e15。

Output

計算結果。

Sample Input #1

4 5
-1 0
1 0
-2 -3
2 -3
4 -5 -1 0 2

Sample Output #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

ch5

出處:

Prof.Wu [管理者： s710426(?0_o)//) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」