Tổng liên tiếp không quá t

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

Cho một mảng gồm \(n\) số nguyên và số nguyên \(t\).

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá \(t\). Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

  • Dòng thứ nhất chứa hai số nguyên \(n,t(1\le n\le 10^5;1\le t\le 10^9)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^4)\)

Output

  • In ra giá trị cần tìm.

Example

Test 1

Input 
4 4
1 2 1 2
Output 
3
Note

Giải thích: Mảng con gồm những phần tử \(a_1,a_2,a_3\) là mảng con có độ dài lớn nhất ta cần tìm vì chúng thoả mãn yêu cầu bài toán.

Bình luận


  • -16
    Lê_Gia_Khánh    5:28 p.m. 7 Tháng 5, 2021 ← đã chỉnh sửa

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • 6
      jumptozero    5:43 p.m. 7 Tháng 5, 2021

      Có lẻ bạn bị nhầm ! Test đầu : \(n =22719 < 100000 = 10^5\)


      • 2
        N7hoatt    9:26 p.m. 7 Tháng 5, 2021

        bài này thêm vào dạng bài two-pointer nữa chứ a


        • 4
          jumptozero    11:25 p.m. 7 Tháng 5, 2021

          Mình đã update!


      • 0
        David    4:02 p.m. 9 Tháng 5, 2021

        :))) ra ngoài mới thấy

        9 bình luận nữa