Guest User

Untitled

a guest
Feb 10th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <string>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <queue>
  11. #include <list>
  12. #include <stack>
  13. #include <cstring>
  14. #include <cstdlib>
  15. #include <complex>
  16. #include <ctime>
  17. #include <bitset>
  18. #include <iomanip>
  19. #include <sstream>
  20. using namespace std;
  21. #define sz(v) ((int)((v).size()))
  22. #define all(v) (v).begin(),(v).end()
  23. typedef long long ll;
  24. typedef pair<int,int> ii;
  25.  
  26. int n;
  27. vector<pair<ll,int>> a, b;
  28. ll bestAns;
  29.  
  30. void rec(int pos, ll curA, ll curB, ll curAns) {
  31. if (pos == n) {
  32. //cerr << "========" << endl;
  33. //for (auto x : a) cerr << x << " "; cerr << endl;
  34. //for (auto x : b) cerr << x << " "; cerr << ", ans = " << curAns << endl;
  35. bestAns = max(bestAns, curAns);
  36. return;
  37. }
  38. for (int i = pos; i < n; i++) {
  39. swap(b[i], b[pos]);
  40.  
  41. ll L = max(curA, curB);
  42. ll R = min(curA + a[pos].first, curB + b[pos].first);
  43. ll add = max(0LL, R - L);
  44. if (a[pos].second != b[pos].second) add = 0;
  45. rec(pos + 1, curA + a[pos].first, curB + b[pos].first, curAns + add);
  46.  
  47. swap(b[i], b[pos]);
  48. }
  49. }
  50.  
  51. void solve() {
  52. while (cin >> n) {
  53. a.resize(n);
  54. b.resize(n);
  55. for (int i = 0; i < n; i++) {
  56. cin >> a[i].first >> b[i].first;
  57. a[i].second = b[i].second = i;
  58. }
  59.  
  60. ll sumA = 0, sumB = 0;
  61. for (int i = 0; i < n; i++) {
  62. sumA += a[i].first;
  63. sumB += b[i].first;
  64. }
  65.  
  66. for (auto& x : a) x.first *= sumB;
  67. for (auto& x : b) x.first *= sumA;
  68.  
  69. bestAns = -1;
  70. for (int shift = 0; shift < n; shift++) {
  71. rec(0, 0, 0, 0);
  72. reverse(all(a));
  73. reverse(all(b));
  74.  
  75. rec(0, 0, 0, 0);
  76. reverse(all(a));
  77. reverse(all(b));
  78.  
  79. vector<pair<ll,int>> newA;
  80. for (int i = 1; i < n; i++) newA.push_back(a[i]);
  81. for (int i = 0; i < 1; i++) newA.push_back(a[i]);
  82. a = newA;
  83. }
  84.  
  85. cout << 1.0 * bestAns / (sumA * sumB) << endl;
  86. }
  87. }
  88.  
  89. int main() {
  90. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);
  91. srand(322);
  92.  
  93. /*for (int n = 3; n <= 64; n++) {
  94. cout << n << ' ';
  95. auto v = solve(n);
  96. cout << sz(v) << endl;
  97. }
  98. cout << "OK" << endl;
  99. return 0;*/
  100.  
  101. //int T;
  102. //cin >> T;
  103. int T = 1;
  104. while (T--) {
  105. //cerr << "===== test started =====" << endl;
  106. solve();
  107. }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment