leetcode

Solution to some Leetcode problems written in C++

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

2463.cpp (930B)

0 class Solution { 1 public: 2 long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory) const { 3 sort(begin(factory), end(factory)); 4 sort(begin(robot), end(robot)); 5 6 vector<int> positions; 7 for (const auto &f : factory) { 8 for (int i = 0; i < f[1]; i++) { 9 positions.push_back(f[0]); 10 } 11 } 12 13 const int n = size(robot), m = size(positions); 14 static long long dp[10001]; 15 16 memset(dp, 0x00, sizeof(dp)); 17 dp[m] = 1e12; 18 for (int i = n - 1; i >= 0; i--) { 19 long long prev = i != n - 1 ? 1e12 : 0; 20 for (int j = m - 1; j >= 0; j--) { 21 long long assign = abs(robot[i] - positions[j]) + prev; 22 long long skip = dp[j + 1]; 23 24 prev = dp[j]; 25 dp[j] = min(assign, skip); 26 } 27 } 28 29 return dp[0]; 30 } 31 };