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

View as PDF

Submit solution


Points: 350
Time limit: 1.0s
Memory limit: 88M

Author:
Problem types

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.

Ví dụ:

Input:

4 4
1 2 1 2

Output:

3

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.

Nguồn: Codeforces.