Advertisement
Guest User

Untitled

a guest
Nov 25th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  5. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  6. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  7. #define FILL(a,value) memset(a, value, sizeof(a))
  8.  
  9. #define SZ(a) (int)a.size()
  10. #define ALL(a) a.begin(), a.end()
  11. #define PB push_back
  12. #define MP make_pair
  13.  
  14. typedef long long LL;
  15. typedef vector<int> VI;
  16. typedef pair<int, int> PII;
  17.  
  18. const double PI = acos(-1.0);
  19. const int INF = 1000 * 1000 * 1000 + 7;
  20. const LL LINF = INF * (LL) INF;
  21.  
  22. const int MAX = 3030;
  23.  
  24. double P[3][MAX];
  25. int n;
  26.  
  27. bool U[MAX];
  28. bool W[MAX];
  29.  
  30. int findMax()
  31. {
  32.     pair<double, int> mx = MP(-1e47, -INF);
  33.    
  34.     FOR (i, 0, n * 3)
  35.     {
  36.         if (U[i]) continue;
  37.        
  38.         mx = max(mx, MP(P[2][i], i));
  39.     }
  40.    
  41.     return mx.second;
  42. }
  43.  
  44. int main()
  45. {
  46.     freopen("in.txt", "r", stdin);
  47.     //ios::sync_with_stdio(false); cin.tie(0);
  48.    
  49.     cin>>n;
  50.    
  51.     FOR (i, 0, 3)
  52.     {
  53.         FOR (j, 0, n * 3)
  54.         {
  55.             cin>>P[i][j];
  56.         }
  57.     }
  58.    
  59.     double sum = 0;
  60.     FOR (j, 0, n * 3)
  61.     {
  62.         sum += P[1][j];
  63.         P[2][j] -= P[1][j];
  64.     }
  65.    
  66.     FOR (j, 0, n)
  67.     {
  68.         int ind = findMax();
  69.         U[ind] = true;
  70.         sum += P[2][ind];
  71.     }
  72.    
  73.     sum = -sum;
  74.    
  75.     FOR (it, 0, n)
  76.     {
  77.         int ind = findMax();
  78.        
  79.         pair<double, int> mx = MP(-1e47, -INF);
  80.        
  81.         FOR (i, 0, n * 3)
  82.         {
  83.             if (W[i]) continue;
  84.            
  85.             double cur = P[0][i] * 2 + P[1][i];
  86.             if (U[i])
  87.             {
  88.                 cur += P[2][i];
  89.                 cur -= P[2][ind];
  90.             }
  91.            
  92.             mx = max(mx, MP(cur, i));
  93.         }
  94.        
  95.         sum += mx.first;
  96.         W[mx.second] = true;
  97.         if (U[mx.second]) U[ind] = true;
  98.     }
  99.    
  100.     sum /= 3;
  101.    
  102.     printf("%.11f\n", sum);
  103.    
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement