Problem: 1376C Social Distance
My Code link: https://ideone.com/Dt76cw
My Approach : I first create a prefix sum array of the given string . Then starting from 1st index say ‘i’ I do a upper_bound operation with prefix_arr[i] value, which gives me the index of postion of 1 occuring after the postion ‘i’.Call it ‘j’ and all the characters in between ‘i’ and ‘j’ are the number of 0. I have also taken in mind the calculation of zeros for the corner cases.
After getting the number of zeroes I subtract ‘k’ from it 2 time or 1 time depending on the position of ‘i’ and ‘j’ . Then I divide the number of zeroes by k+1 and increment the count by this value. Also if the there is any remainder >=1 ,it is also increments the count.
Then I update the value of i as the psotion ‘j’ and continue looping.
Please help me and tell what is wrong with my code.