leetcode

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

0638.cpp (1273B)

      1 class Solution {
      2     static bool finished(const vector<int> needs) {
      3         for (const int n : needs)
      4             if (n) return false;
      5         return true;
      6     }
      7 
      8   public:
      9     int shoppingOffers(const vector<int> &price, const vector<vector<int>> &special, const vector<int> &needs,
     10                        int offer = 0, int cost = 0) const {
     11         if (finished(needs)) return cost;
     12 
     13         const int n = size(price);
     14 
     15         int res = cost;
     16         for (int i = 0; i < n; i++) {
     17             res += needs[i] * price[i];
     18         }
     19 
     20         for (int i = offer; i < size(special); i++) {
     21             int times = INT_MAX;
     22             for (int j = 0; j < n && times; j++) {
     23                 if (!special[i][j]) continue;
     24                 times = min(times, needs[j] / special[i][j]);
     25             }
     26 
     27             if (!times) continue;
     28 
     29             vector<int> next = needs;
     30             int added = 0;
     31 
     32             for (int k = 1; k <= times; k++) {
     33                 added += special[i].back();
     34                 if (cost + added >= res) break;
     35                 for (int j = 0; j < n; j++)
     36                     next[j] -= special[i][j];
     37                 res = min(res, shoppingOffers(price, special, next, i + 1, cost + added));
     38             }
     39         }
     40 
     41         return res;
     42     }
     43 };