Problem statement is here: http://codeforces.com/contest/230/problem/A
The problem is not difficult, what makes it even easier it that even O(n^2) solution is accepted by the judge.
If you consider each Dragon as a struct of strength
that it possesses and the bonus
it gives then the problem becomes a matter of sorting Dragons that can be killed by the player’s initial strength
. I have sorted using a custom comparator which makes life a lot easy. Here is the code:
#include <bits/stdc++.h> struct Dragon { int strength; int bonus; Dragon(int strength, int bonus) : strength(strength), bonus(bonus) {} }; bool comparator(Dragon i, Dragon j) { return i.strength < j.strength; } int main() { int player_strength; int num_dragons; std::cin >> player_strength >> num_dragons; std::vector<Dragon> dragons; for (int i = 0; i < num_dragons; i++) { int strength, bonus; std::cin >> strength >> bonus; dragons.push_back(Dragon(strength, bonus)); } std::sort(dragons.begin(), dragons.end(), comparator); for(Dragon dragon : dragons) { if(dragon.strength < player_strength) { player_strength+=dragon.bonus; } else { std::cout<<"NO"; return 0; } } std::cout<<"YES"; return 0; }
Please let me know in comments if you have found a more optimal way to solve the problem. Cheers!