leetcode

Solution to some Leetcode problems written in C++

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

0638.cpp (1273B)

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