時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
沿岸有 N 棟依序排列的建物，第 i 棟遭破壞的損失為 d_i。每一次海嘯侵襲的範圍是一段非空連續區間，其嚴重程度等於區間內所有建物的損失總和。
把所有 N(N+1)/2 個區間依嚴重程度由大到小排列，求第 K 個區間的嚴重程度。不同區間即使總損失相同，也各自占一個名次。
輸入格式
第一行為 N、K，以空白分隔，其中 1 ≤ N ≤ 5×10^5，1 ≤ K ≤ N(N+1)/2。 第二行為 N 個非負整數 d_i，其中 0 ≤ d_i ≤ 10^9。第 i 棟與第 i+1 棟相鄰。
輸出格式
輸出一個整數，表示第 K 嚴重情況的損失總和。
原題分組限制
20 分：N ≤ 1000；20 分：N ≤ 5000；20 分：N ≤ 50000；40 分：無額外限制。
範例 1
輸入：
3 2
1 2 4
輸出：
6
範例 2
輸入：
3 4
1 2 3
輸出：
3
來源
TOI 2021 年 5 月練習賽潛力組，依官方 PDF 整理。
官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202105/Tsunami.pdf
標籤：TOI 歷屆
範例測資
範例輸入 1
3 2 1 2 4
範例輸出 1
6
範例輸入 2
3 4 1 2 3
範例輸出 2
3
請先登入後再提交程式碼
討論與題解
載入討論區…