Dragons 230A

In this problem, Kirito has to fight a number of dragons. Every dragon has a strength, and if Kirito defeats it, he gains some bonus strength. If he manages to defeat all the dragons, he climbs to the next round.

So our task is to predict whether Kirito can clear all the dragons or not.

Approach:

My first intuition was that this looks like a standard greedy scheduling problem. Kirito has to fight dragons in some order, and at every step we want to make the locally optimal choice so that future fights become easier.

you can understand scheduling problem easily by solving https://cses.fi/problemset/task/1629/

The first thing I noticed is that defeating a dragon increases Kirito's strength. That means the earlier we gain strength, the more useful it becomes for the remaining fights.

Now suppose there are two dragons available. One is weaker and one is stronger. If I can defeat the weaker dragon first, I gain its bonus strength and become stronger before facing the harder one. But if I try the stronger dragon first, there is a chance I lose immediately and never get the bonus from the weaker dragon.

So it makes sense to fight the weakest dragons first.

That observation suggests sorting the dragons by their strength in ascending order.

After sorting, I simply go through the dragons one by one.

If Kirito's current strength is strictly greater than the dragon's strength, he wins the fight and gains the bonus strength from that dragon.

Otherwise, if Kirito cannot defeat a dragon at some point, then he cannot continue the journey, so the answer is "NO".

If he successfully defeats every dragon, then the answer is "YES".

#include<bits/stdc++.h>
using namespace std;
 
    typedef  long long   ll;
   
    #define yep cout << "YES\n"
    #define nope cout << "NO\n"
  
    void solve();
  int   main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    
    return 0;
}
void solve() {
    ll s,n;
    cin >> s>>n;
    vector<pair<ll, ll>> dragon;
    for (ll i=0; i < n; i++){

        ll a, b;
        cin >> a >> b;
        dragon.push_back({a, b});
    }
    ll power = s;

    ll win = 0;
    sort(dragon.begin(), dragon.end());
     for (ll i=0; i < n; i++){
        if(dragon[i].first<power){
            win++;
            power += dragon[i].second;
        }
     }
     if(win==n)
         yep;
     else
         nope;
    }

Complexity:

Sorting O(n log n).

The traversal takes O(n).

So the overall complexity is O(n log n).