Bedao Testing Contest 01 - KTHSUM
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
Bình luận
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).