分数: 6 点
警告
2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
给你一个长度序列 N: A = (A_1, A_2, \dots, A_N).
对于非空连续子序列 B of A,让分数为 B 是元素总和的绝对值 B.
假设我们已经计算了所有 \frac{N(N+1)}{2} 的非空连续子序列 A。找到 K- 这些分数中最小的。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq K \leq \frac{N(N+1)}{2}
- -10^9 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \dots A_N
输出
打印 K- 这些分数中最小的。
示例输入 1
2 2 2 -3
示例输出 1
2
的非空连续子序列 A 及其分数如下。
- 序列 (A_1) 的得分为 | 2 | = 2.
- 序列 (A_2) 的得分为 | -3 | = 3.
- 序列 (A_1, A_2) 的得分为 | 2 + (-3) | = 1.
示例输入 2
5 10 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 2
3000000000
请注意,答案可能不适合 32位整数。
示例输入 3
7 22 3 -1 4 -1 5 -9 2
示例输出 3
5