時間限制 1000 ms ・ 記憶體限制 512 MB
題目描述
林場在數線 [0,L] 上，N 棵樹的位置為 c_i，高度為 h_i。樹向左倒覆蓋 [c_i−h_i,c_i]，向右倒覆蓋 [c_i,c_i+h_i]。只要能選一側，使倒下範圍不超出林場且不壓到其他仍站立的樹，就可砍除。其他樹剛好在倒下範圍端點時不算壓到。 砍倒後立即移除該樹，持續砍除直到無樹可砍。已知最後能砍的樹與順序無關。求砍除數量及其中最大樹高。
輸入格式
第一行為正整數 N、L，N ≤ 100000，L ≤ 10^9。第二行依座標遞增給 N 個正座標，各不超過 L；第三行給對應的 N 個正高度，各不超過 10^9。
輸出格式
第一行輸出砍除棵數；第二行輸出被砍樹的最大高度。若一棵也不能砍，第二行輸出 0。
範例測資
範例輸入 1
6 140 10 30 50 70 100 125 30 15 55 10 55 25
範例輸出 1
4 30
範例輸入 2
1 10 5 6
範例輸出 2
0 0
請先登入後再提交程式碼
討論與題解
載入討論區…