Bedao Testing Contest 01 - KTHSUM

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một mảng ~A~ gồm ~N~ số nguyên. Như bạn đã biết, trên mảng này có tổng cộng ~\frac{N(N + 1)}{2}~ đoạn con liên tiếp. Bạn được yêu cầu in ra đoạn con liên tiếp có tổng lớn thứ ~K~ (Đoạn con liên tiếp có tổng lớn thứ 1 là đoạn con liên tiếp có tổng lớn nhất mảng).

Input

Dòng đầu tiên gồm hai số nguyên ~N~ và ~K~ ~(1 \le N \le 10^5)~ ~(1 \le K \le \frac{N(N + 1)}{2})~.

Dòng thứ hai gồm ~N~ số nguyên mô tả mảng ~A~ ~(-10^9 \le A_i \le 10^9)~.

Output

In ra một số nguyên duy nhất là giá trị của đoạn con liên tiếp có tổng lớn thứ ~K~.

Sample Input 1

3 1
1 2 3

Sample Output 1

6

Sample Input 2

3 1
-1 -2 -3

Sample Output 2

-1

Subtask

  • ~50\%~ số test có ~N \le 1000~
  • ~50\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.



  • 3
    from_somewhere_with_love   commented on Sept. 23, 2021, 6:22 p.m. edited

    Dùng policy based data structure thì mới accept được 50% test còn lại TLE. Độ phức tạp O(nlogn)*O(log 2^50).