Kích thước mảng con lớn nhất

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử số nguyên dương và một số nguyên dương \(K\). Tìm mảng con liên tục có kích thước lớn nhất sao cho tất cả các mảng con liên tục có kích thước bé hơn hoặc bằng nó đều có tổng các phần tử nhỏ hơn \(K\).

Input

  • Dòng đầu là chứa số nguyên \(N\) (\(N \leq 10^6\)) và số nguyên \(K\) (\(K \leq 10^{12}\))
  • Dòng thứ 2 ghi \(N\) số nguyên thuộc dãy, các số cách nhau bởi dấu cách.

Output

  • Ghi kích thước mảng con lớn nhất cần tìm.

Example

Test 1

Input 
4 8
1 2 3 4
Output 
2

Test 2

Input 
4 8
1 2 10 4
Output 
-1
Note

Trong ví dụ 1, tổng dãy con có:

  • Độ dài 1: 1,2,3,4
  • Độ dài 2: 3,5,7
  • Độ dài 3: 6,9
  • Độ dài 4: 10

Bình luận