leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2463.cpp (930B)

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