PIPIOJ

Problem D: k大子段和

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 153 Solved: 28
[Submit] [Status] [Web Board] [Creator:]

给出 $n$ 个整数 $a_1,a_2,...,a_n$ ，定义 $b_{i,j}=a_i+a_{i+1}+...+a_j(1\le i\le j\le n)$ ，找出所有的 $b_{i,j}$ 中第 $k$ 大的是多少。

第一行两个整数 $n,k(1\le n\le 100000,1\le k\le \frac{n*(n+1)}{2})$ 。
第二行 $n$ 个整数 $a_1,a_2,...,a_n(1\le a[i]\le 10^9)$ 。

输出一行一个整数表示答案。

3 2
2 1 3

$b_{1,1}=2,b_{1,2}=3,b_{1,3}=6,b_{2,2}=1,b_{2,3}=4,b_{3,3}=3$
从大到小排序后为 $6,4,3,3,2,1$
第二大的为 $4$

[Submit][Status]