Link đề bài: http://vnoi.info/problems/show/NKMAXSEQ/
Đề bài:
Cho dãy số nguyên a1, a2, …, an. Dãy số ai, ai+1, …, aj 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 ai+ai+1…+aj đượ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 ai 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 ≤ n ≤ 50000; |ai| ≤ 20000; |p| ≤ 10^9. Có 50% số lượng test với n ≤ 2000.