fork download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int N;
  5. int A[16], B[16], K[16], L[16];
  6. int visited; // 비트
  7. int val, mx;
  8. void func(int cnt) {
  9. if (cnt == N) {
  10. mx = max(mx, val);
  11. return;
  12. }
  13. int nxt = -1, nxtmn = 1000000007;
  14. for (int i = 0; i < N; i++) {
  15. if (visited & (1 << i)) continue;
  16. if ((visited & K[i]) == K[i]) {
  17. if (L[i]) {
  18. visited ^= (1 << i);
  19. val += (cnt + 1) * B[i];
  20. func(cnt + 1);
  21. val -= (cnt + 1) * B[i];
  22. visited ^= (1 << i);
  23. }
  24. else if (nxtmn > B[i]) nxtmn = B[i], nxt = i;
  25. }
  26. }
  27.  
  28. if (nxt > -1) {
  29. int i = nxt;
  30. visited ^= (1 << i);
  31. val += (cnt + 1) * B[i];
  32. func(cnt + 1);
  33. val -= (cnt + 1) * B[i];
  34. visited ^= (1 << i);
  35. }
  36. }
  37.  
  38. int main() {
  39. ios::sync_with_stdio(0);
  40. cin.tie(0);
  41.  
  42. cin >> N;
  43. for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  44. for (int i = 0; i < N; i++) {
  45. for (int j = i + 1; j < N; j++) {
  46. if (A[j] % A[i] == 0) K[j] |= (1 << i), L[i] |= (1 << j);
  47. }
  48. }
  49.  
  50. func(0);
  51. cout << mx;
  52. }
Time limit exceeded #stdin #stdout 5s 5280KB
stdin
16
96 96
48 48
24 24
12 12
6 6
3 3
32 32
16 16
8 8
4 4
2 2
1 1
97 97
95 95
91 91
96 96
stdout
Standard output is empty