BZOJ2490 Zombie’s Treasure Chest

 1 /**************************************************************
 2     Problem: 2490
 3     User: rausen
 4     Language: C++
 5     Result: Accepted
 6     Time:4 ms
 7     Memory:804 kb
 8 ****************************************************************/
 9  
10 #include <cstdio>
11 #include <algorithm>
12  
13 using namespace std;
14 typedef long long ll;
15  
16 ll v, s1, s2, v1, v2;
17 ll ans, del;
18  
19 int main() {
20     int T, icase, i;
21     ll t, tmp;
22     scanf("%d", &T);
23     for (icase = 1; icase <= T; ++icase) {
24         scanf("%lld%lld%lld%lld%lld", &v, &s1, &v1, &s2, &v2);
25         if (s1 < s2) swap(s1, s2), swap(v1, v2);
26         tmp = s1 * s2 / __gcd(s1, s2), t = v / tmp;
27         v = v % tmp;
28         if (t) --t, v += tmp;
29         ans = max(t * (tmp / s1) * v1, t * (tmp / s2) * v2);
30         for (i = del = 0; i <= v / s1; ++i)
31             del = max(del, i * v1 + (v - i * s1) / s2 * v2);
32         printf("Case #%d: %lld\n", icase, ans + del);
33     }
34     return 0;
35 }