leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2033.cpp (744B)

0 class Solution { 1 public: 2 int minOperations(const vector<vector<int>> &grid, int x) const { 3 static int dp[100001]; 4 vector<int> vec; 5 6 for (const auto &row : grid) 7 vec.insert(end(vec), begin(row), end(row)); 8 sort(begin(vec), end(vec)); 9 10 for (int i = 0, acc = 0; i < size(vec) - 1; i++) { 11 const int crnt = vec[i + 1] - vec[i]; 12 if (crnt % x) return -1; 13 dp[i + 1] = acc += (i + 1) * crnt; 14 } 15 16 int res = INT_MAX; 17 for (int i = size(vec) - 1, acc = 0; i > 0; i--) { 18 acc += (size(vec) - i) * (vec[i] - vec[i - 1]); 19 res = min(res, acc + dp[i - 1]); 20 } 21 22 return res != INT_MAX ? res / x : 0; 23 } 24 };