oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

justright Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

justright.html

Problem Description

Gug is going on a mushroom-collecting holiday. He has a list of N cities that he wants to visit, and each city i has Ai mushrooms within it.

Gug has to choose a consecutive segment of cities in his list to visit, and he will collect all the mushrooms within the cities he visits. Therefore, he has N*(N+1)/2 possible holidays, and each will yield a specific number of mushrooms.

Gug knows that too little mushrooms are bad, and too much mushrooms are also bad. He wants to go on a holiday such that the number of mushrooms collected is the Kth largest possible among all the holidays he could have chosen.

Find the number of mushrooms collected in the holiday that Gug chooses to go on.

Input

The first line of input will contain two integers, N and K.
The second line of input will contain N integers, representing the array A.

Output

The output should contain one line with one integer, the number of mushrooms collected by Gug in his holiday.

Limits

For all subtasks: 1 ≤ K ≤ N*(N+1)/2, 1 ≤ Ai ≤ 109.

Subtask 1 (27%): 1 ≤ N ≤ 1000.

Subtask 2 (8%): 1 ≤ N ≤ 200000, K = 1.

Subtask 3 (9%): 1 ≤ N ≤ 200000, K = N*(N+1)/2.

Subtask 4 (20%): 1 ≤ N ≤ 200000, Ai = 1.

Subtask 5 (36%): 1 ≤ N ≤ 200000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

5 6
1 2 3 4 5

Sample Output 1

9

Sample Input 2

5 1
3 1 4 1 5

Sample Output 2

14

Tags

Sliding Window, Binary Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
127221s256MBMinimum
28211s256MBMinimum
39201s256MBMinimum
420201s256MBMinimum
5361021s256MBMinimum
6021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o justright -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.