1703

# define ll long long
class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        ll i, n = nums.size(), l, r;
        vector<ll> a;   // Indexes array
        a.push_back(0); // To make indexes array the same size as prefix array
        for(i=0; i<n; i++)
            if(nums[i])
                a.push_back(i);
        n = a.size();

        vector<ll> prefix(n, 0);  // Prefix array
        for(i=1; i<n; i++)     // prefix[i] = sum of all elements from a[0] to a[i]
            prefix[i] = prefix[i - 1] + a[i];

        ll ans = LONG_LONG_MAX;

        // Rolling window [l...r] of length k
        for(l=1,r=k; r<n; ++l, ++r) {
            ll mid = (l + r) / 2;  // Mid-point - current element
            ll radius = mid - l;   // How many elements on each side
            ll right = prefix[r] - prefix[mid];     // Prefix of radius elements to the right of mid
            ll left = prefix[mid - 1] - prefix[l - 1];  // Prefix of radius elements to the left of mid
            ll subtract = (radius) * (radius + 1);  // Once all elements are equal, make it a sequence
            if(k % 2 == 0) {        // Special case if k is even
                subtract += (a[mid] + (radius + 1));     // Deduct current element and also deduct the cost of the furthest right element
            }
            ans = min(ans, right - left - subtract);
        }
        return ans;
    }
};