Submit solution
Points:
0.12 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho dãy số nguyên ~a_{1}~, ~a_{2}~, ..., ~a_{n}~.
Dãy số ~a_{i}~, ~a_{i + 1}~, ..., ~a_{j}~ với ~1 \leq i \leq j \leq n~ được gọi là dãy con của dãy số đã cho và khi đó, ~j-i + 1~ được gọi là độ dài, còn ~a_{i} + a_{i~ + ~1}~ ...~+ a_{j}~ được gọi là trọng lượng của dãy con này.
Yêu cầu: cho số nguyên ~p~, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn ~p~ hãy tìm dãy con có độ dài lớn nhất.
Input
- Dòng đầu tiên ghi hai số nguyên ~n~ và ~p~ cách nhau bởi dấu cách.
- Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa số nguyên ~a_{i}~ là số hạng thứ ~i~ của dãy số đã cho, ~i = 1~, ~2~, ..., ~n~.
Output
Ghi ra số nguyên ~k~ là độ dài của dãy con tìm được (qui ước: nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì ~k = -1)~.
Giới hạn
- Trong tất cả các test: ~1 \leq n \leq 50000~; ~|a_{i}| \leq 20000~; ~|p| \leq 10^{9}~.
- Có ~50\%~ số lượng test với ~n \leq 2000~.
Sample Input 1
5 6
-2
3
2
-2
3
Sample Output 1
4
Sample Input 2
4 9
2
3
2
-2
Sample Output 2
-1
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
dùng segment tree để cắn đc nlogn còn n thì chịu =)))
O(n^2) nhưng cũng tùy bạn của bạn cài đặt nhé. Nếu bạn ý viết tối giản thì AC cũng không quá là khó!