INS14A-BSTRING

BSTRING

Given below c++ code is for ins14a spoj or bstring spoj.

Hint :- Think of bringing all one's to it median in windows of 'm' ones.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 18 October 2015 (Sunday) 22:05
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        char s[50009];
        ll m;
        scanf("%lld %s" , &m ,s);
        int n = strlen(s);
        vector<ll> position;
        position.pb(0);
        for(int i = 0 ; i < n ; i++)
            if(s[i] == 49)
                position.pb(i+1);
        ll median = m/2 + 1;
        ll left = 0 , right = 0;
        for(int i = 0 ; i < median ; i++)
            left += position[i];
        for(int i = median + 1 ; i<=m ; i++)
            right += position[i];
        ll ans = right - left + (2*median - m - 1)*position[median];
        int var_median = median;
        for(int i = m+1 , j = 1 ; i < position.size() ;j++, i++){
            left -= position[j];
            left += position[var_median];
            var_median++;
            right -= position[var_median];
            right += position[i];
            ll temp = right - left + (2*median - m - 1)*position[var_median];
            ans = min(ans , temp);
        }
        ans -= (m*m + 2*median*(median - 1) - 2*m*median + m)/2;
        printf("%lld\n", ans);
    }
    return 0;
}