Mã bài:
noeldecor
Điểm:
1,6 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Sắp tới mùa Noel, cậu bé
được mẹ cho ~S~ đơn vị tiền và dự định sẽ dùng số tiến đó để mua một chuỗi các hạt châu để trang trí cho cây thông. Ở cửa hàng, người ta treo một dãy ~n~ hạt châu có giá trị lần lượt là ~a_1, a_2, a_3, ..., a_n~. sẽ được lựa chọn một đoạn liên tiếp các hạt châu sao cho tổng giá tiền của chúng không vượt quá ~S~. Vì cây thông khá to nên chuỗi càng dài thì trang trí càng đẹp. Vì hôm nay bận đi ăn sinh nhật của , các bạn hãy giúp chọn một chuỗi dài nhất để trang trí nhé!Input
- Dòng đầu tiên chứa hai số nguyên ~n, S~ - lần lượt là độ dài chuỗi hạt châu mà cửa hàng treo, số tiền mà có;
- Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.
Output
- In ra một dòng duy nhất là độ dài đoạn hạt châu liên tiếp dài nhất mà có thể mua với ~S~ đơn vị tiền. Nếu không thể mua được đoạn hạt châu nào, in ra ~0~.
Giới hạn
- Trong tất cả các subtask, ~S \le 10^{12}~.
- Subtask ~1~: ~40\%~ số test có ~n \le 100~;
- Subtask ~2~: ~40\%~ số test khác có ~n \le 2000~;
- Subtask ~3~: ~20\%~ số test còn lại có ~n \le 10^5~.
Sample Input
7 20
10 2 7 3 9 4 1
Sample Output
4
Giải thích
Ta chọn đoạn ~[3, 9, 4, 1]~ có độ dài là ~4~ và có tổng là ~17 \le S = 20~.
Bình luận