c050. 202201_4. 牆上海報

Content

有一個由 $n$ 個木板所組成的柵欄，每個木板的高度為 $h[1], h[2], ..., h[n]$，有 $k$ 張海報要張貼在柵欄上，每張海報的寬度為 $w[1], w[2], \cdots, w[n]$ 並且高度均為 $1$。

若要張貼海報在高度為 $x$ 的高度，則第 $i$ 張海報需要張貼在一個長度為 $w[i]$ 的連續並且高度都不小於 $x$ 的木板上，且每張海報張貼的高度需要一致、按照順序並不能重疊 (可以相連)。詢問最高可以貼到多高的位置。

Input

第一行有兩個正整數 $n, k$，接下來一行有 $n$ 個正整數代表每個木板的高度，最後一行有 $k$ 個正整數代表每張海報的寬度。

數字範圍

$1 \leq n \leq 200000$
$1 \leq k \leq 5000$
$1 \leq h[i] \leq 10^9$
$\sum{w[i]} \leq n$

子題配分

(20%): $1\leq n \leq 100, k=1$
(40%): $k=1$
(40%): 無額外限制

Output

輸入最大可以張貼的高度。

Sample Input #1

5 1
6 3 7 5 1
3

Sample Output #1

Sample Input #2

10 3
5 3 7 5 1 7 5 3 8 4
2 2 1

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1K
公開測資點#3 (5%): 2.0s , <1K
公開測資點#4 (5%): 2.0s , <1M
公開測資點#5 (5%): 2.0s , <1K
公開測資點#6 (5%): 2.0s , <1M
公開測資點#7 (5%): 2.0s , <10M
公開測資點#8 (5%): 2.0s , <1K
公開測資點#9 (5%): 2.0s , <1K
公開測資點#10 (5%): 2.0s , <1K
公開測資點#11 (5%): 2.0s , <1K
公開測資點#12 (5%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <1M
公開測資點#16 (5%): 2.0s , <1M
公開測資點#17 (5%): 2.0s , <1M
公開測資點#18 (5%): 2.0s , <1M
公開測資點#19 (5%): 2.0s , <1K

Hint ：

範例 2
柵欄長相如下圖，三張海報 (寬度為 2, 2, 1) 可以貼在高度為 $5$ 的高度。

Tags:

出處:

2022年1月 APCS 演算法海牛 [管理者： ktlai (K．我已霸榜．Tlai) ]

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