## Mock CCC '18 Contest 5 S4 - Sparse Binary String Counting

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type

Given a binary string of length , where exactly characters are ones, compute the number of substrings that have at least three ones.

#### Constraints

are presented in sorted order.

In tests worth marks, you may assume .

In tests worth an additional marks, you may assume .

#### Input Specification

The first line of the input contains two space-separated integers, and .

Each of the next lines contains a single integer, , indicating that character of the string is a one.

#### Output Specification

Output a single integer, the number of substrings that contain at least three ones.

#### Sample Input

5 4
1
2
4
5

#### Sample Output

3