bit全探索(ABC 104 C問題)

問題

以下ネタバレ注意

1. ll p[10], c[10];
2. int main() {
3. int D, G;
4. cin >> D >> G;
5. REP(i, D) {
6. cin >> p[i] >> c[i];
7. }
8. ll ans = INF;
9. bool used[10];
10. REP(i, 10)used[i] = false;
11. //各配点の問題を解ききるかどうかで全探索(2^10通り)
12. for (int x = 0; x < myPow(2, D, m); x++) {
13. //例えばD = 10なら000000000000~1111111111を調べるので10進数だと0~1023
14. int sum = 0;
15. ll cnt = 0;
16. for (int i = 0; i < D; i++) {
17. if (x&(1 << i)) {//右からi桁目が1ならば
18. used[i] = true;
19. sum += 100 * (i + 1)*p[i] + c[i];
20. cnt += p[i];
21. }
22. }
23. if (sum >= G) {
24. ans = min(ans, cnt);
25. }
26. else {
27. REPR(i, D-1) {
28. if (!used[i]) {
29. REP(j, p[i]+1) {
30. sum += 100 * (i + 1);
31. cnt++;
32. if (sum >= G) {
33. ans = min(ans, cnt);
34. break;
35. }
36. }
37. }
38. }
39. }
40. REP(i, 10)used[i] = false;
41. }
42. cout << ans << endl;
43. }