Two pointer 2C
Xem PDF
Điểm:
800 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Given an array of \(n\) integers \(a_i\). Let's say that the segment of this array \(a[l..r] (1≤l≤r≤n)\) is good if the sum of elements on this segment is at most \(s\). Your task is to find the number of good segments.
Input
- The first line contains integers \(n\) and \(s\) \((1≤n≤10^5, 1≤s≤10^{18})\).
- The second line contains integers \(a_i (1≤a_i≤10^9)\).
Output
- The number of good segments.
Example
Input
7 20
2 6 4 3 6 8 9
Output
19
Nguồn: Codeforces
Bình luận
Dịch đề: Cho 1 đoạn Ai có n phần tử. Gọi đoạn con A[l..r] (1 <= l <= r <= n) là đẹp nếu tổng của cả đoạn con không lớn hơn s. Nhiệm vụ của bạn là đếm số đoạn con đẹp trong mảng.