← 返回题目列表

AtCoder · abc155_d

D. 对

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有 N 整数 A_1, A_2, ..., A_N.

有 \frac{N(N-1)}{2} 选择其中两个并组成一对的方法。如果我们计算每一对的乘积并按升序对结果进行排序,那么 K该列表中的第一个数字?

约束

  • 输入中的所有值都是整数。
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq \frac{N(N-1)}{2}
  • -10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

4 3
3 3 -4 -2

示例输出 1

-6

有六种方式可以形成配对。这些对的产品是 9, -12, -6, -12, -6, 8.

按升序对这些数字进行排序,我们有 -12, -12, -6, -6, 8, 9。此列表中的第三个数字是 -6.


示例输入 2

10 40
5 4 3 2 -1 0 0 0 0 0

示例输出 2

6

示例输入 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

示例输出 3

448283280358331064