아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

생선

시간 제한1초메모리 제한64 MB

요약
합이 K 이상인 연속 부분 배열의 개수를 센다.
난이도

보통10점 중 7점

유형
누적 합, 분할 정복, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

고양이 쿠칭은 생선을 좋아한다. 그런데 너무 큰 생선을 사 버려서 전부 먹고 싶지는 않다. 쿠칭은 생선을 머리부터 꼬리까지 NN개의 조각으로 자르고 1번부터 NN번까지 번호를 붙인 다음, 각 조각에 만족도를 매겼다. 만족도가 클수록 그 조각을 먹을 때 더 즐겁다. 생선은 덩어리로 먹어야 맛있다. 한 덩어리는 번호가 연속한 조각 하나 이상으로 이루어진다.

쿠칭은 입맛이 까다로워서 만족도의 합이 KK보다 작은 덩어리는 즐기지 못한다. 즉 합이 KK 이상이어야 한다. 쿠칭이 즐겁게 먹을 수 있는 덩어리 하나를 생선에서 잘라내는 방법이 몇 가지인지 구하라. 덩어리에 들어가지 않은 조각은 버린다.

한 덩어리는 조각을 최소 1개 포함하고, 최대 NN개까지, 즉 생선 전체까지 포함할 수 있다.

입력

첫째 줄에 32비트 부호 있는 정수 NN과 KK가 주어진다. NN은 항상 양수이고, KK는 양수일 수도 0 이하일 수도 있다. (1≤N≤200,0001 \le N \le 200{,}000)

둘째 줄에 조각 NN개의 만족도가 순서대로 주어진다. ii번째 정수는 ii번째 조각의 만족도이다. 만족도는 32비트 부호 있는 정수 범위에 들어가며, 양수일 수도 0 이하일 수도 있다.

출력

쿠칭이 즐겁게 먹을 수 있는 덩어리, 곧 만족도의 합이 KK 이상인 덩어리를 하나 잘라내는 방법의 수를 정수 하나로 출력한다.

힌트

첫 번째 예제에서 쿠칭은 생선을 5조각으로 나누었고 만족도는 차례로 1, -2, 3, -4, 5이며, 합이 2 이상인 덩어리만 즐긴다. 조건을 만족하는 덩어리는 (1, -2, 3), (1, -2, 3, -4, 5), (-2, 3, -4, 5), (3), (3, -4, 5), (5)의 여섯 가지다. 나머지 덩어리는 합이 KK보다 작다. 1번, 3번, 5번 조각은 연속하지 않으므로 (1, 3, 5)는 덩어리가 아니다.

예제2

  1. 예제 1

    입력
    5 2
    1 -2 3 -4 5
    
    예상 출력
    6
    
  2. 예제 2

    입력
    5 -2
    1 -2 3 -4 5
    
    예상 출력
    13