전설의 용사는 마왕을 물리치기 위해 성검의 조각을 모으고 있다.
성검은 총 N개의 조각으로 나뉘어 있으며, 각 조각의 신성한 힘은 Bisto로 주어진다.
용사는 연속된 구간의 조각들을 하나로 합쳐 임시 무기를 만들 수 있다.
하나의 무기의 힘은 해당 구간에 포함된 조각 힘의 합으로 정의된다.
용사는 정확히 K 이상의 힘을 가진 무기를 만들 수 있는 연속 구간의 개수를 알고 싶어 한다.
즉, 구간 [l, r]에 대해
Bisto[l] + Bisto[l+1] + ... + Bisto[r] >= K
를 만족하는 연속 구간의 개수를 구하여라.
첫째 줄에 정수 N, K가 주어진다.
둘째 줄에 N개의 정수 Bisto1, Bisto2, ..., BistoN이 공백으로 구분되어 주어진다.
힘의 합이 K 이상인 연속 구간의 개수를 출력한다.
1 ≤ N ≤ 300,0001 ≤ Bistoi ≤ 10^91 ≤ K ≤ 10^18
5 7
2 3 4 1 5
4 10
1 2 3 4
8
1
조건을 만족하는 구간은 다음과 같다.
[1,3]
[1,4]
[1,5]
[2,3]
[2,4]
[2,5]
[3,5]
[4,5]
따라서 가능한 무기의 개수는
8
개이다.
전체 구간
[1,4]
의 합만
10
이므로 정답은
1
이다.
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
Bisto = list(map(int, input().split()))
answer = 0
current_sum = 0
right = 0
for left in range(N):
while right < N and current_sum < K:
current_sum += Bisto[right]
right += 1
if current_sum >= K:
answer += N - right + 1
current_sum -= Bisto[left]
print(answer)