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 }