XXVI Olimpíada Brasileira de Informática
Soma
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 e K 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.Restrições
- 1 ≤ N ≤ 500000 (5 x 105)
- 0 ≤ K ≤ 106
- 0 ≤ Xi ≤ 100 para 1 ≤ i ≤ N
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 10 pontos, N ≤ 500
- Em um conjunto de casos de teste somando 20 pontos, N ≤ 104
- Em um conjunto de casos de teste somando 30 pontos, K>0 e Xi>0 para 1 ≤ i ≤ N
- Em um conjunto de casos de teste somando 40 pontos, nenhuma restrição adicional (\sl note que para esta subtarefa o inteiro da saída pode não caber em 32 bits.)
Exemplos
Exemplos
Entrada
10 4 2 0 1 1 0 0 8 4 1 3 |
Saída
5 |
Entrada
15 0 0 0 0 0 0 5 12 0 1 0 0 0 51 0 0 |
Saída
25 |
