Apartment hunting
user_3741288
c_cpp
a year ago
1.2 kB
7
Indexable
#include <unordered_map> #include <vector> using namespace std; void func(vector<unordered_map<string, int>>& dp, vector<unordered_map<string, bool>>& blocks, int st, int inc) { unordered_map<string, int> temp; for(int i=st; i>=0 && i<blocks.size(); i=i+inc) { unordered_map<string, int> temp1 = temp; for(auto ele=blocks[i].begin(); ele!=blocks[i].end();ele++) { if(temp1.find(ele->first) == temp1.end()) { temp1[ele->first] = ele->second == true ? i : INT_MAX; } else { temp1[ele->first] = ele->second == true ? i : temp1[ele->first]; } } temp = temp1; dp[i] = temp1; } } int apartmentHunting( vector<unordered_map<string, bool>> blocks, vector<string> reqs ) { int n=blocks.size(); vector<unordered_map<string, int>> dp1(n), dp2(n); func(dp1, blocks, 0, 1); func(dp2, blocks, blocks.size()-1, -1); int ind=0, mini=INT_MAX; for(int i=0;i<n;i++) { int l_max = 0; for(int j=0;j<reqs.size();j++) { l_max = max(l_max, min(abs(i-dp1[i][reqs[j]]), abs(i-dp2[i][reqs[j]]))); } if(l_max < mini) { mini = l_max; ind = i; } } return ind; }
Editor is loading...
Leave a Comment