The Question I wanna ask is given below:
https://codeforces.com/problemset/problem/1216/F#

I know it's on different platform but still wanna ask for help because I got to know that Google recently asked this question.

I was not able to solve the question but then I saw few solutions... All of them seem logicial and fine(ofcourse those are working solution).

The question I have is what is the proof of the correctness of the solution given below. And if you can provide with some other solution.. I would love to hear it.

Below is the code I wrote following the tutorial
Code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;string str;
cin>>n>>k>>str;
int routerOnRight[n+2];
routerOnRight[n+1] = n+1;
for(int i=n;i>0;i--){
if(str[i-1]=='1')
routerOnRight[i] = i;
else
routerOnRight[i] = routerOnRight[i+1];
}
long long dp[n+1];
dp[0] = 0;
for(int i=1;i<=n;i++)
{
dp[i] = dp[i-1]+i;//here we are taking the case when we are getting direct connection
int routerPos = routerOnRight[max(1,i-k)];//here we wanna choose the nearest router the current position preferablily on left
// on left because I have already done computation of indexes on the left

    if(routerPos==n+1 || routerPos>i+k)//first case means I didn't find any router which current node can be in range, 
    // second case means we got the router but it's out of range
    {
        continue;
    }
    dp[i] = min(dp[i],routerPos+dp[max(1,routerPos-k)-1]);
}
cout<<dp[n];

}