Informatica Online Judge

  평균 평균 #5 [1797 / 0705]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 39   Total Tried : 47


The Champion of this Problem (C++) : gs17018 - ms / 743byte
My Best Submission (C++) : N/A

[koistudy.net (34st 김현수)]

Background

음이 아닌 정수로 구성된 길이 $N$의 수열이 있다.

이 수열에서 $1$개 이상의 연속한 수들을 뽑을 때, 그 수들의 평균이 $P$이상인 경우의 수를 구하여라.

Input

첫 번째 줄에 N이 주어진다. ($1 ≤ N ≤ 300,000$)
두 번째 줄에 수열의 값 A[i]가 주어진다. ($0 ≤ A[i] ≤ 1,000,000,000$)
세 번째 줄에 P가 주어진다. ($0 ≤ P ≤ 1,000,000,000$)


[입력값의 정의역]
Subtask #1 : N ≤ 500
Subtask #2 : N ≤ 5,000
Subtask #3 : N ≤ 300,000, 모든 A[i]가 P이하
Subtask #4 : N ≤ 300,000, A[i] 중 0보다 큰 수가 3개 이하로 들어온다.
Subtask #5 : 제약 조건 없음.

Output

평균이 $P$이상인 부분 수열의 경우의 수를 출력하여라.

IO Example

입력
4
2 3 4 1
3

출력
4

예시 설명
{3},{4},{3,4},{2,3,4}

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]