Submeta sua solução

Arquivo:

Linguagem: Selecione C++17 / g++ C17 / gcc Javascript Java / JDK Python 3 / CPython

Submete

Nome do arquivo: sanduiche.x, onde x deve ser c, cpp, java, js ou py

Sanduíche

Você está na Seletiva para a IOI e depois de um dia cansativo de provas, chegou a hora do jantar. Hoje, trouxeram um sanduíche muito longo cortado em N pedaços de diversos tamanhos diferentes. Você gostaria de comer uma quantidade total de sanduíche de comprimento D, porém há uma regra: para evitar bagunça, você só pode ou pegar uma sequência contínua de pedaços, ou pegar pedaços das extremidades. Você sabe a sequência C₁, C₂, ...\ C_N dos comprimentos dos pedaços na ordem em que estão posicionados no sanduíche. Agora, para otimizar o seu jantar, quer fazer um programa que com esses dados responda de quantas formas você pode escolher os pedaços do sanduíche que vai comer. Em outras palavras, deve contar quantos pares (i, j), 1 ≤ i ≤ j ≤ N, existem tais que o somatório C_i + C_i+1 + ... + C_j seja igual a D e quantos pares (i, j), 1 ≤ i < j ≤ N, existem tais que o somatório C₁ + C₂ + ... + C_i + C_j + C_j+1 + ... + C_N seja igual a D.

Entrada

A primeira linha contém dois inteiros N e D, representando respectivamente o número de pedaços e a quantidade de sanduíche que você quer comer. A segunda linha contém N inteiros C₁, C₂, ... \ C_N, onde C_i é o tamanho do i-ésimo pedaço.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o número de maneiras de comer pedaços de sanduíche com soma D.

Restrições

• 2 ≤ N ≤ 10⁶.
• 1 ≤ D ≤ 10⁹.
• 1 ≤ C_i ≤ 10³.

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a 20 pontos, N ≤ 200.
• Em um conjunto de casos de teste equivalente a 40 pontos, N ≤ 1000.

Exemplos

Entrada 5 10 1 2 3 4 3

Saída 3

 

Entrada 5 5 1 1 1 1 1

Saída 5

 

Entrada 9 618 665 658 248 282 428 562 741 290 457 5

Saída 0