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; }