algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (1589B)


      1 #include <vector>
      2 #include <algorithm>
      3 #include <iostream>
      4 #include <unordered_map>
      5 #include <utility>
      6 
      7 long long findBest(std::vector<std::pair<long long,long long>>& nums, std::unordered_map<long long,long long>& best, std::size_t idx) {
      8 
      9     if(idx >= nums.size()) {
     10         return 0;
     11     }
     12 
     13     if(best[nums[idx].first] != -1) {
     14         return best[nums[idx].first];
     15     }
     16     
     17     int nextIndex = idx+1;
     18 
     19     if(nextIndex >= nums.size()) {
     20         best[nums[idx].first] = nums[idx].second * nums[idx].first;
     21         return nums[idx].second * nums[idx].first;
     22     }
     23 
     24     if(nums[nextIndex].first == nums[idx].first + 1) {
     25         long long take = findBest(nums,best,idx+2) + nums[idx].second * nums[idx].first;
     26         long long skip = findBest(nums,best,idx+1);
     27         long long res = std::max(take, skip);
     28         best[nums[idx].first] = res;
     29         return res;
     30     } else{
     31         long long res = findBest(nums,best,idx+1) + nums[idx].second * nums[idx].first;
     32         best[nums[idx].first] = res;
     33         return res;
     34     }
     35 }
     36 
     37 int main() {
     38 
     39     int sz;
     40     std::cin >> sz;
     41     
     42     std::unordered_map<long long,long long> nums {};
     43     std::unordered_map<long long,long long> best {};
     44 
     45     for(int i = 0; i < sz; ++i) {
     46         int cur;
     47         std::cin >> cur;
     48         nums[cur] += 1;
     49         best[cur] = -1;
     50     }
     51     
     52     std::vector<std::pair<long long,long long>> numVec {};
     53     for(auto& pr : nums) {
     54         numVec.push_back(std::pair {pr.first,pr.second});
     55     }
     56 
     57     std::sort(numVec.begin(), numVec.end());
     58     std::cout << findBest(numVec, best, 0) << std::endl;
     59     
     60 }