Leet Code

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        
        const int n = (int)nums.size();
        vector <long long> pref, suff;
        long long sum = 0, back = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 1)
            {
                sum += (i-back);
                pref.push_back(sum);
                // back = i;
            }
        }

        sum = 0, back = n-1;
        for (int i = n-1; i >= 0; i--)
        {
            if (nums[i] == 1)
            {
                sum += (back-i);
                suff.push_back(sum);
                // back = i;
            }
        }
        reverse(suff.begin(), suff.end());
        vector <long long> ones;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 1)
            ones.push_back(i);
        }

        const int sz = (int)ones.size();
        int ans = INT_MAX;
        for (int i = 0; i < sz; i++)
        {
            int l = (k-1)/2;
            int r = (k-1)-l;
            // cout << i << " " << l << " " << r << endl;
            if (i-l >= 0 && i+r < sz)
            {
            ans = min(ans, (int)(pref[i+r]-pref[i]-(r)*ones[i] + suff[i-l]-suff[i]-(l)*(n-ones[i]-1)-((l*(l+1))/2 + (r*(r+1))/2)));
            }
            if (i-r >= 0 && i+l < sz)
            ans = min(ans, (int)(pref[i+l]-pref[i]-(l)*ones[i] + suff[i-r]-suff[i]-(r)*(n-ones[i]-1)-((l*(l+1))/2 + (r*(r+1))/2)));
            
        }

        return ans;
    }
};