CFR 526 C. Om Nom and Candies ( Enumeration )

Problem - C - Codeforces
If we can have more than LCM( wr, wb ) candies, not losing generality assuming hr / wr > hb / wb, the optimal solution will take at least

many red candies. After processing those, we will have c % lcm( wr, wb ) candies left. Now we can enumerate for the candies left.
If lcm( wr, wb ) < sqrt( 1e9 ), c % lcm( wr, wb ) < sqrt( 1e9 ).
Else if lcm( wr, wb ) >= sqrt( 1e9 ), max( wr, wb ) >= sqrt( 1e9 ), c / max( wr, wb ) < sqrt( 1e9 ).
Overall time complexity O( sqrt( N ) ). So many overflow issues I had..

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1e9 + 9;
typedef unsigned long long ull;

ull c, hr, hb, wr, wb;

void solve(){
    if( (double)hr / wr < (double)hb / wb ){
        swap( hr, hb );
        swap( wr, wb );
    }
    ull lcm = wr * wb / __gcd( wr, wb );
    ull ans = 0ULL;
    if( c / lcm > 1ULL ){
        ans = ( c / lcm - 1 ) * lcm / wr * hr;
        c -= ( c / lcm -  1 ) * lcm;
    }
    if( wr < wb ){
        swap( hr, hb );
        swap( wr, wb );
    }
    ull best = 0ULL;
    for(ull i = 0; i * wr <= c; ++i){
        ull j = ( c - i * wr ) / wb;
        best = max<ull>( best, (ull)i * hr + (ull)j * hb );
    }
    cout << ans + best << endl;
}

int main(){
    cin >> c >> hr >> hb >> wr >> wb;
    solve();
    return 0;
}