Dragons

Dragons
Codeforces easy

Kirito must defeat all \(n\) dragons on a level of a game. His strength is initially \(s\). The \(i\)-th dragon has strength \(x_i\).

  • If Kirito fights the \(i\)-th dragon and his strength is not greater than \(x_i\), he loses.
  • Otherwise he defeats the dragon, and his strength increases by \(y_i\).

Kirito can fight the dragons in any order. Determine whether he can defeat all dragons without a single loss.

Constraints:

  • \(1 \le s \le 10^4\), \(1 \le n \le 10^3\)
  • \(1 \le x_i \le 10^4\), \(0 \le y_i \le 10^4\)

Input:

  • First line: two integers \(s\) and \(n\).
  • Next \(n\) lines: two integers \(x_i\) and \(y_i\) — the strength of the \(i\)-th dragon and the bonus for defeating it.

Output:

  • YES if Kirito can defeat all dragons, and NO otherwise.

Example:

Input:

2 2
1 99
100 0

Output:

YES

(Kirito defeats the first dragon, his strength becomes \(2 + 99 = 101\), and then he defeats the second dragon.)

Solution

Kirito’s strength never decreases, so it is always best to fight the weakest remaining dragon first: if Kirito cannot defeat the weakest remaining dragon, he cannot defeat any other remaining dragon either.

We store each dragon in a struct with two members, sort the dragons by strength with a custom comparator, and fight them in this order. If some dragon has strength at least \(s\), the answer is NO.

Sorting takes \(O(n \log n)\) time.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Dragon {
    int strength;
    int bonus;
};

bool weaker(Dragon a, Dragon b) {
    return a.strength < b.strength;
}

int main() {
    int s, n;
    cin >> s >> n;

    vector<Dragon> dragons(n);
    for (int i = 0; i < n; i++) {
        cin >> dragons[i].strength >> dragons[i].bonus;
    }

    sort(dragons.begin(), dragons.end(), weaker);

    for (int i = 0; i < n; i++) {
        if (s <= dragons[i].strength) {
            cout << "NO\n";
            return 0;
        }
        s += dragons[i].bonus;
    }

    cout << "YES\n";
}