← 返回题目列表

AtCoder · past202109_l

L. K 次 Abs

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

分数: 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