Informatica Online Judge

  반 배정 [2358 / 0936]

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


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

[36th 이민규 (gs18080)]
Writer ID : [gs18080]

Background

학기 초가 되어 학생들의 반을 새로 배정해야 한다. n명의 학생들의 겹치지 않는 등수가 순서대로 주어질 때, 연속한 학생들을 골라서 한 학급을 만들어야 한다. 이때 학급의 "평등함"이 정의되는데, 평등함이 m이상이 되게 학생들을 학급에 배정하는 경우의 수를 구하는 것이 문제이다.

평등함은 아래와 같이 계산된다

학생들의 등수가 $a_{i}$ $(1 \leq i \leq n)$ 일때
$s$번째 학생부터 $e$번째 학생들을 골랐고 $(1 \leq s \leq e \leq n)$, 고른 학생들 끼리의 새로운 등수를
$b_{k}$ $(s \leq k \leq e , 1 \leq b_{k} \leq e-s+1)$ 이라고 정의하자

이때 평등함 = $\sum_{k = s}^{e}{a_{k} \times b_{k}}$ 이다

Input

첫 줄에 학생들의 인원수 n 과, 평등함의 기준 m이 주어진다. 둘째 줄에 n명의 학생들의 등수 $a_{i}$ $(1 \leq i \leq n,1 \leq a_{i} \leq n)$ 이 주어진다.


주어지는 값의 제약조건은 아래와 같다.

n $(1 \leq n \leq 5 \times 10^{5})$ , m $(0 \leq m \leq 5 \times 10^{16})$

Output

학급의 평등함이 m이상이 되게 한 학급을 만드는 가짓수를 출력한다.

IO Example

입력
3 2
1 2 3

출력
5


입력
10 30
1 2 3 4 10 6 7 8 9 5

출력
34

* 보충 설명 : 학급은 하나만 만들어야 하며, 학급에 배정되지 않은 학생도 존재할 수 있다.

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