NKMAXSEQ - Dãy con dài nhất
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 ≤ i ≤ j ≤ 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.
Dữ liệu vào
- 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.
Kết qủa
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).
Hạn chế
Trong tất cả các test: 1 ≤ n ≤ 50000; |a i | ≤ 20000; |p| ≤ 10 9 . Có 50% số lượng test với n ≤ 2000.
Ví dụ
Dữ liệu mẫu 5 6 -2 3 2 -2 3 Kết qủa 4 Dữ liệu mẫu 4 9 2 3 2 -2 Kết qủa -1
- Người up: paulmcvn
- Nguồn bài: Ðề thi quốc gia 2006