CB_079 Đếm số đoạn con liên tiếp có tổng lớn hơn hoặc bằng V

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 501M
Input: stdin
Output: stdout

Dạng bài

CB_079 Đề bài — Đếm số đoạn con có tổng ≥ V Cho mảng A gồm n phần tử và một số nguyên V. Hãy đếm xem có bao nhiêu đoạn con liên tiếp (subarray) của mảng A có tổng các phần tử trong đoạn đó lớn hơn hoặc bằng V. Dữ liệu vào: • Dòng 1: gồm 2 số nguyên n và V (1 ≤ n ≤ 10⁶, 1 ≤ V ≤ 10¹²) • Dòng 2: gồm n số nguyên A₁, A₂, ..., Aₙ (0 ≤ Aᵢ ≤ 10⁹) Dữ liệu ra: • In ra số lượng đoạn con liên tiếp có tổng ≥ V. Ví dụ: Input: 3 4 1 2 3 Output: 2 Giải thích: Có 2 đoạn con thỏa mãn: • A[2]..A[3] = 2 + 3 = 5 ≥ 4 • A[1]..A[3] = 1 + 2 + 3 = 6 ≥ 4


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.