Iamtui1010

acmnb

Nov 10th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<queue>
  6. #include<array>
  7.  
  8. #define long long long
  9. #define nln '\n'
  10.  
  11. const long N = 4*1e5 + 10;
  12.  
  13. using namespace std;
  14.  
  15. // GLobal variables: n
  16.  
  17. long n;
  18. vector<long> a, b;
  19. priority_queue<array<long, 3>, vector<array<long,3>>, less<array<long, 3>>> pqu;
  20. vector<pair<long, long>> pic;
  21.  
  22. void pick()
  23. {
  24.     long n1 = n/2, n2 = n/2;
  25.  
  26.     while (!pqu.empty())
  27.     {
  28.         auto tak = pqu.top();
  29.         pqu.pop();
  30.  
  31.         if (n1 == 0)
  32.         {
  33.             pic.push_back({tak[1], 2});
  34.             continue;
  35.         }
  36.         if (n2 == 0)
  37.         {
  38.             pic.push_back({tak[1], 1});
  39.             continue;
  40.         }
  41.  
  42.         if (tak[2] == 1)
  43.         {
  44.             --n1;
  45.             pic.push_back({tak[1], tak[2]});
  46.             continue;
  47.         }
  48.  
  49.         if (tak[2] == 2)
  50.         {
  51.             --n2;
  52.             pic.push_back({tak[1], tak[2]});
  53.         }
  54.     }
  55. }
  56.  
  57. void code()
  58. {
  59.     long ans = 0;
  60.     for (const auto &i : pic)
  61.         //cout << i.first << ": " << i.second << nln;
  62.         if (i.second == 1)
  63.             ans += a[i.first];
  64.         else
  65.             ans += b[i.first];
  66.     cout << ans << nln;
  67. }
  68.  
  69. void data()
  70. {
  71.     cin >> n;
  72.     n *= 2;
  73.     a.resize(n+1, 0);
  74.     b.resize(n+1, 0);
  75.     for (long i = 1; i <= n; ++i)
  76.     {
  77.         cin >> a[i] >> b[i];
  78.         long per = -1;
  79.         if (a[i] <= b[i])
  80.             per = 1;
  81.         else
  82.             per = 2;
  83.         pqu.push({abs(a[i]-b[i]), i, per});
  84.     }
  85. }
  86.  
  87. void process()
  88. {
  89.     pick();
  90.     code();
  91. }
  92.  
  93. int main()
  94. {  
  95.     data();
  96.     process();
  97.     return 0;
  98. }
  99.  
Advertisement
Add Comment
Please, Sign In to add comment