Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <set>
- #include <map>
- #include <deque>
- #include <queue>
- #include <list>
- #include <stack>
- #include <cstring>
- #include <cstdlib>
- #include <complex>
- #include <ctime>
- #include <bitset>
- #include <iomanip>
- #include <sstream>
- using namespace std;
- #define sz(v) ((int)((v).size()))
- #define all(v) (v).begin(),(v).end()
- typedef long long ll;
- typedef pair<int,int> ii;
- int n;
- vector<pair<ll,int>> a, b;
- ll bestAns;
- void rec(int pos, ll curA, ll curB, ll curAns) {
- if (pos == n) {
- //cerr << "========" << endl;
- //for (auto x : a) cerr << x << " "; cerr << endl;
- //for (auto x : b) cerr << x << " "; cerr << ", ans = " << curAns << endl;
- bestAns = max(bestAns, curAns);
- return;
- }
- for (int i = pos; i < n; i++) {
- swap(b[i], b[pos]);
- ll L = max(curA, curB);
- ll R = min(curA + a[pos].first, curB + b[pos].first);
- ll add = max(0LL, R - L);
- if (a[pos].second != b[pos].second) add = 0;
- rec(pos + 1, curA + a[pos].first, curB + b[pos].first, curAns + add);
- swap(b[i], b[pos]);
- }
- }
- void solve() {
- while (cin >> n) {
- a.resize(n);
- b.resize(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i].first >> b[i].first;
- a[i].second = b[i].second = i;
- }
- ll sumA = 0, sumB = 0;
- for (int i = 0; i < n; i++) {
- sumA += a[i].first;
- sumB += b[i].first;
- }
- for (auto& x : a) x.first *= sumB;
- for (auto& x : b) x.first *= sumA;
- bestAns = -1;
- for (int shift = 0; shift < n; shift++) {
- rec(0, 0, 0, 0);
- reverse(all(a));
- reverse(all(b));
- rec(0, 0, 0, 0);
- reverse(all(a));
- reverse(all(b));
- vector<pair<ll,int>> newA;
- for (int i = 1; i < n; i++) newA.push_back(a[i]);
- for (int i = 0; i < 1; i++) newA.push_back(a[i]);
- a = newA;
- }
- cout << 1.0 * bestAns / (sumA * sumB) << endl;
- }
- }
- int main() {
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);
- srand(322);
- /*for (int n = 3; n <= 64; n++) {
- cout << n << ' ';
- auto v = solve(n);
- cout << sz(v) << endl;
- }
- cout << "OK" << endl;
- return 0;*/
- //int T;
- //cin >> T;
- int T = 1;
- while (T--) {
- //cerr << "===== test started =====" << endl;
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment