28a Olimpíada Brasileira de Informática
Submeta sua solução

Chuva

Eventos climáticos extremos como chuvas descomunais estão cada vez mais frequentes e intensos em todo o mundo. O Centro Nacional de Monitoramento da Nlogônia tem medidores de quantidade de chuva dia-a-dia espalhados por todo o reino. Cada medição é um número inteiro, indicando a quantidade de chuva, em milímetros, que caiu na Nlogônia num determinado dia. Como o sistema existe há vários anos, a lista de medições é muito grande. Preocupado com o assunto, o rei da Nlogônia mandou que o Ministro da Ciência crie um programa de computador para calcular quantos intervalos de dias existem na lista de medições tal que a soma das medições nesse intervalo é igual a um certo valor. Mais precisamente, considere uma lista com N medições, indicando a quantidade de chuva do dia 1 ao dia N. Considere ainda todos os possíveis intervalos de dias entre 1 e N, cada intervalo definido pelo dia inicial e dia final do intervalo. O rei deseja saber quantos intervalos têm a soma das medições exatamente igual a um certo valor S. O Ministro da Ciência é um físico brilhante, mas não sabe resolver essa tarefa. Você poderia ajudá-lo?

Entrada

A primeira linha contém um inteiro N, o número de medições na lista. A segunda linha contém um inteiro S, o valor da soma desejada. A terceira linha contém N inteiros Xi, os valores das medições.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, que deve ser o número de intervalos que têm a soma das medições igual a S.

Restrições

  • 1 ≤ N ≤ 100 000
  • 0 ≤ S ≤ 1 000 000
  • 0 ≤ Xi ≤ 10, para 1 ≤ i ≤ N

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 20 pontos, N ≤ 300.
  • Para um outro conjunto de casos de testes valendo 30 pontos, N ≤ 1000.

Exemplos

Entrada
6
2
0 2 0 1 0 1
Saída
6
	

 

Entrada
8
13
10 1 0 0 9 10 1 5
Saída
0
	

 

Entrada
5
6
1 0 3 0 2
Saída
1
	

 

PJ P1 P2 PS
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação