Find total number of substrings with 1's greater than 0's, need optimization

Question

Given and string we need to find out the total number of substrings in which 1's are greater than 0's.

I approached this problem using Dynamic programming but I was not able to come up with a solution, I am successful in writing a naive-logic but I was not able to optimize the code (i.e time limit is exceeding)

Any help in optimizing or suggestions for a new approach will be help full. The time complexity of below code is O(n^3) Any solutions to reduce the time-complexity will be helpfull.

Thank in advance.

Code I used:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int tc =0; //total count
    string st; //original string
    getline(cin,st);
    int lent = st.size(); //size of string
    for(int i =0;i<lent;i++){ //loop to generate all possible substrings
        int j = lent-1;
        while(j>=i){
            
            string st1(st.begin()+i,st.end()-j+i); // A substring
            int c1 = count(st1.begin(),st1.end(),'1'); // count of 1's in substring
            if(c1 > st1.size()-c1) tc++; // Condition to check if 1's are more
            j--;
        }
    }
    cout << tc; // Print total substrings
}

Note: A substring is a contiguous sequence of characters within a string. For more information about substrings visit Wikipedia

Answer 1

Treat respectively '0' and '1' as integers 1 and -1. Then the string becomes an integer array. Calculate its prefix sum array s, i.e., s[0] = 0 and s[i] = a[0] + ... + a[i - 1]. Now every substring with number of '1's > number of '0's corresponds to a pair (i, j) such that i < j and s[i] > s[j]. You can then use the trick in find total number of (i,j) pairs in array such that i<j and a[i]>a[j]. The time complexity is O(n log n).