URI Online Judge | 3051

Soma

Por BR Brazil

Timelimit: 2

Temos uma sequência de N quadrados desenhados lado a lado. Cada quadrado possui um número natural anotado dentro dele. Dados a sequência dos N quadrados e um valor K , quantos retângulos distintos existem cuja soma dos números dentro do retângulo é exatamente igual a K? Por exemplo, a figura mostra uma sequência de N = 10 quadrados para a qual existem 5 retângulos cuja soma dos números é igual a K = 4.

Entrada

A primeira linha da entrada contém dois inteiros N (1 ≤ N ≤ 5 × 105) e K (0 ≤ K ≤ 106) representando o número de quadrados na sequência e o valor da soma desejada. A segunda linha da entrada contém N números naturais Xi , para 1 ≤ i ≤ N, indicando a sequência de números anotados dentro dos quadrados.

Saída

Seu programa deve imprimir uma linha contendo um número inteiro representando quantos retângulos existem na sequência cuja soma é igual a K.

Exemplos de Entrada Exemplos de Saída

10 4

2 0 1 1 0 0 8 4 1 3

5

15 0

0 0 0 0 0 5 12 0 1 0 0 0 51 0 0

25