VOI 06 Bài 7 - Dãy con dài nhất
Xem dạng PDF
Gửi bài giải
Điểm:
0,12 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
Bình luận
tôi đã suy nghĩ bài này trong 36 tỷ năm, làm được 360 dòng code, tôi vận dụng hết 36 kế sách tôi tự nghĩ ra và tôi chỉ đúng được 36 test nhất định mà do tôi tự nghĩ ra tôi đã submit bài này 36 lần và cả 36 lần ko lần nào đúng
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
trau la buffalo a ban
oách xà lách vô cùng
tôi cũng thích ăn salad
Chúc các bạn một ngày tốt lành:33
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
có nhé bạn, xem tại đây