Codeforces Round #112 (Div. 2)(C. Another Problem on Strings)

 Bismillahir Rahmanir Rahim

///Author: Tanvir Ahmmad

///CSE,Islamic University,Bangladesh

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

#include<sstream>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<vector>

#include<iterator>

#include <functional> ///sort(arr,arr+n,greater<int>()) for decrement of array

/*every external angle sum=360 degree

  angle find using polygon hand(n) ((n-2)*180)/n*/

///Floor[Log(b)  N] + 1 = the number of digits when any number is represented in base b

using namespace std;

typedef long long ll;

int main()

{

    ll n,cnt=0,bro=0;

    map<ll,ll>mp;

    map<ll,ll>::iterator it;

    string str;

    cin>>n>>str;

    if(n)

    {

        ll sz=str.size(),arr[sz+3],k=0;

        for(ll i=0; i<sz; i++)

        {

            if(str[i]=='1')

                arr[k++]=i,mp[i]=bro,bro=0;

            else

                bro++;

        }

        arr[k++]=sz,mp[sz]=bro;

        for(ll i=0; i<k-n; i++)

        {

            ll pre=arr[i],post=arr[i+n];

            it=mp.find(pre);

            ll cnt_pre=it->second;

            it=mp.find(post);

            ll cnt_post=it->second;

            if(max(cnt_post,cnt_pre)==0)

                cnt++;

            else if(min(cnt_post,cnt_pre)==0 && max(cnt_post,cnt_pre)!=0)

                cnt+=(max(cnt_post,cnt_pre)+1);

            else

                cnt+=(1+cnt_pre+cnt_post+(cnt_pre*cnt_post));

        }

        cout<<cnt<<endl;

    }

    else

    {

        for(ll i=0;i<str.size();i++) 

        {

            if(str[i]=='0') bro++;

            else cnt+=(bro*(bro+1)/2),bro=0;

        }

        if(bro) cnt+=(bro*(bro+1)/2),bro=0;

        cout<<cnt<<endl;

    }

    return 0;

}

///Alhamdulillah

Problem Link:https://codeforces.com/problemset/problem/165/C