Đếm dãy con liên tiếp có tổng bằng k
Xem dạng PDF
Gửi bài giải
Điểm:
14,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho số nguyên dương ~𝑛~ và dãy số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~.
Yêu cầu: Hãy cho biết có bao nhiêu dãy con gồm các phần tử liên tiếp nhau có tổng đúng bằng ~𝑘~.
Dữ liệu vào:
- Dòng đầu ghi hai số nguyên dương ~𝑛~, ~𝑘~ (~1 ≤ 𝑛 ≤ 10^6; 𝑘 ≤ 10^9~)
- Dòng thứ hai ghi lần lượt các số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~(~1 ≤ 𝑎_𝑖 ≤ 10^6~)
Kết quả:
- Ghi một số nguyên cho biết kết quả bài toán.
Ví dụ:
Input
6 8
4 3 5 2 1 8
Output
3
Ràng buộc:
- Có 30% số test tương ứng với 30% số điểm có ~𝑛 ≤ 200~;
- Có 30% số test khác tương ứng 30% số điểm có ~𝑛 ≤ 2000~;
- Có 20% số test khác tương ứng 20% số điểm có ~𝑛 ≤ 2 × 10^5~;
- Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm
Bình luận
hãy dislike coment này để tôi leo top bảng xếp hạng từ dưới đếm lên:>>>