Bit strings

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;


int l[N], r[N], z[N], a[N];
int c[N];
void solve()
{
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    memset(z, 0, sizeof(z));
    memset(a, 0, sizeof(a));

    string s;
    cin >> s;

    int m = s.length(), k=0;
    int last = -1;
    for(int i=0; i<m; i++)
    {
        z[i] = z[i-1];
        if(s[i]=='1')
        {
            // in one
            k++;
            if(last == -1)
            {
                l[k] = z[i];
            } else {
                l[k] = r[k-1] = z[i] - z[last];
            }
            last = i;
        } else {
            // in zero
            z[i]+=1;
        }
    }
    r[k] = z[m-1] - z[last];

    for(int i=1; i<=k; i++)
    {
        a[0] += c[l[i]];
        for(int j=0; i+j<=k; j++)
        {
            // if(l[i] == 0 && r[i+j] == 0)
            //     continue;
            // // a[j+1] += (l[i]>0? l[i]:1) * (r[i+j]>0? r[i+j]:1);
            a[j+1] += (l[i] + 1) * (r[i+j] + 1);
        }
    }
    a[0] += c[r[k]];

    for(int i=0; i<=m; i++)
    {
        // all numbers
        cout<<a[i]<<" ";
    }
    cout<<endl;
}


signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    c[1] = 1;
    for(int i=2; i<=1e5; i++)
        c[i] = c[i-1]+i;

    while (t--) {
        solve();
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED