RSQ
Probably overkill, but I couldn\'t think of a simpler way during the contest.\n\nIdea: every subarray of nums whose sum is k corresponds to a candidate solution
Probably overkill, but I couldn\'t think of a simpler way during the contest.\n\nIdea: every subarray of `nums` whose sum is `k` corresponds to a candidate solution where we move all the `1`\'s in the subarray together. To analyze the cost of the candidate, consider the cost, for each `0` in the subarray, of swapping that `0` to an extreme (either the leftmost part or the rightmost part of the subarray). The cost of swapping to the left is the number of `1`s to the left of that `0`, and the cost of swapping to the right is the number of `1`s to the right of that `0`. E.g.:\n\n`1101 -> 0111` cost is 2\n`1101 -> 1110` cost is 1\n\nEach `0` can be moved to an extreme independently.\n\n`11010 -> 00111` cost is 2+3=5\n`11010 -> 01110` cost is 2+0=2\n`11010 -> 11100` cost is 1+0=1\n\nIn general, for a subarray, the cost is the sum over all `0`\'s of `min(# 1\'s to the left, # 1\'s to the right)`. Note that all the `0`\'s which are to the right of less than `K/2` ones can move optimally to the left, and all the `0`\'s which are to the left of less than `K/2` zeroes can move optimally to the right. \n\nHence we can precompute the number of `1`s to the left and to the right of each `0` , and when evaluating a candidate\'s cost, do two range sums (one over the `0`\'s which move to the left, and one over those which move optimally to the right). However, we overcount the number of `1`\'s that are outside of the candidate subarray when doing the range sum; we can fix this by subtracting the overcount (for the left range sum, this is the number of `1`\'s to the left of the subarray, multiplied by the number of `0`\'s in the left range sum\'s interval).\n\nNote that the range sums are actually done offline, so you can speed this up by a `log(N)` factor if you want.\n\n```\nclass Solution {\npublic:    \n    int minMoves(vector<int>& nums, int k) {\n        vector<int> ones_pos;\n        vector<vector<int>> trials;\n\n        auto left = BIT(nums.size());\n        auto right = BIT(nums.size());\n        \n        auto zeroes = BIT(nums.size());\n                \n        for (int i=0; i<nums.size(); i++) {\n            if (nums[i] == 1) {\n                ones_pos.push_back(i);\n            } else {\n                zeroes.pointSet(i, 1);\n            }\n        }\n        \n        int rs = 0;\n        for (int i=0; i<nums.size(); i++) {\n            if (nums[i] == 1) {\n                rs++;\n            } else {\n                left.pointSet(i, rs);\n            }\n        }\n        \n        rs = 0;\n        for (int i=nums.size()-1; i>=0; i--) {\n            if (nums[i] == 1) {\n                rs++;\n            } else {\n                right.pointSet(i, rs);\n            }\n        }\n        \n        \n        int p=0;\n        int s=k-1;\n        int r = (k-1) / 2;\n        while (s < ones_pos.size()) {\n            trials.push_back({ones_pos[p], ones_pos[r], ones_pos[s]});\n            p++; r++; s++;\n        }\n        \n        long long left_boost = 0;\n        long long right_boost = ones_pos.size()-k;\n        \n        long long ret = LLONG_MAX;\n                \n        for (const auto& trial : trials) {\n            // cout << "trying" << trial << endl;\n            int p = trial[0], q = trial[1], r = trial[2];\n            \n            long long left_cost = left.rangeSum2(p, q) - left_boost*zeroes.rangeSum2(p,q);\n            long long right_cost = right.rangeSum2(q, r) - right_boost*zeroes.rangeSum2(q, r);\n            \n            long long candidate = left_cost + right_cost;\n            \n            left_boost++;\n            right_boost--;\n            \n            // cout << "candidate=" << left_cost << "+" << right_cost << "=" << candidate << endl;\n            ret = min(ret, candidate);\n        }\n        \n        return ret;\n    }\n};\n\nstruct BIT {\n\tvector<long long> s;\n\tBIT(int n) : s(n) {}\n\tvoid pointSet(int pos, long long dif) { // a[pos] += dif\n\t\tfor (; pos < s.size(); pos |= pos + 1) s[pos] += dif;\n\t}\n\tlong long rangeSum(int pos) { // sum of values in [0, pos)\n\t\tlong long res = 0;\n\t\tfor (; pos > 0; pos &= pos - 1) res += s[pos-1];\n\t\treturn res;\n\t}\n  long long rangeSum2(int a, int b) { // sum of values in [a, b]\n    return rangeSum(b+1) - rangeSum(a);\n  }\n};\n```
[]