algorithms

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

commit e3e22e30175cbe2eb0a81bbf88973886da6f0813
parent a7193be38bcbdb7c5aecc00a97217120260bbf9b
Author: Andrew Laack <andrew@laack.co>
Date:   Fri, 16 Oct 2026 19:22:44 -0500

Boredom

Diffstat:
Acomp/boredom/.main.cpp.swp | 0
Acomp/boredom/ex1.in | 2++
Acomp/boredom/ex2.in | 2++
Acomp/boredom/ex3.in | 2++
Acomp/boredom/main.cpp | 60++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/boredom/problem.txt | 61+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 127 insertions(+), 0 deletions(-)

diff --git a/comp/boredom/.main.cpp.swp b/comp/boredom/.main.cpp.swp Binary files differ. diff --git a/comp/boredom/ex1.in b/comp/boredom/ex1.in @@ -0,0 +1,2 @@ +2 +1 2 diff --git a/comp/boredom/ex2.in b/comp/boredom/ex2.in @@ -0,0 +1,2 @@ +3 +1 2 3 diff --git a/comp/boredom/ex3.in b/comp/boredom/ex3.in @@ -0,0 +1,2 @@ +9 +1 2 1 3 2 2 2 2 3 diff --git a/comp/boredom/main.cpp b/comp/boredom/main.cpp @@ -0,0 +1,60 @@ +#include <vector> +#include <algorithm> +#include <iostream> +#include <unordered_map> +#include <utility> + +long long findBest(std::vector<std::pair<long long,long long>>& nums, std::unordered_map<long long,long long>& best, std::size_t idx) { + + if(idx >= nums.size()) { + return 0; + } + + if(best[nums[idx].first] != -1) { + return best[nums[idx].first]; + } + + int nextIndex = idx+1; + + if(nextIndex >= nums.size()) { + best[nums[idx].first] = nums[idx].second * nums[idx].first; + return nums[idx].second * nums[idx].first; + } + + if(nums[nextIndex].first == nums[idx].first + 1) { + long long take = findBest(nums,best,idx+2) + nums[idx].second * nums[idx].first; + long long skip = findBest(nums,best,idx+1); + long long res = std::max(take, skip); + best[nums[idx].first] = res; + return res; + } else{ + long long res = findBest(nums,best,idx+1) + nums[idx].second * nums[idx].first; + best[nums[idx].first] = res; + return res; + } +} + +int main() { + + int sz; + std::cin >> sz; + + std::unordered_map<long long,long long> nums {}; + std::unordered_map<long long,long long> best {}; + + for(int i = 0; i < sz; ++i) { + int cur; + std::cin >> cur; + nums[cur] += 1; + best[cur] = -1; + } + + std::vector<std::pair<long long,long long>> numVec {}; + for(auto& pr : nums) { + numVec.push_back(std::pair {pr.first,pr.second}); + } + + std::sort(numVec.begin(), numVec.end()); + std::cout << findBest(numVec, best, 0) << std::endl; + +} diff --git a/comp/boredom/problem.txt b/comp/boredom/problem.txt @@ -0,0 +1,61 @@ +# Problem + +A. Boredom +time limit per test +1 second +memory limit per test +256 megabytes + +Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it. + +Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player. + +Alex is a perfectionist, so he decided to get as many points as possible. Help him. +Input + +The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence. + +The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105). + +--- + +# Constraints + +- step + - choose an element of the sequence + - delete it + - delete all elements with n-1 or n+1 values where n was the value of the deleted element + - player then gets n points + +- perform as many steps as needed, score the most points + +--- + +# Thoughts + +- can we just sort the collection and iterate in reverse over it? + - this would be an greedy approach + - this breaks down when we have multiple instances of the same number +- hmm, would we have to do the dp version of this? + +--- + +# Examples + +2 +1 2 + +take 2 because it's the largest value + + +3 +1 2 3 + +Take 3, take 2 + +9 +1 2 1 3 2 2 2 2 3 + +leave 3, take 2 + +2 * 5 = 10