Advertisement
kasougi

Untitled

Jan 26th, 2022
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6.  
  7. typedef unsigned long long ull;
  8.  
  9.  
  10. std::vector <int> vec;
  11. long double sum = 0.0;
  12.  
  13. void sift_up(int i);
  14. void sift_down(int i);
  15.  
  16. void push(int tmp) {
  17.     vec.push_back(tmp);
  18.     int size = (int)(vec.size())-1;
  19.     sift_up(size);
  20. }
  21.  
  22. void sift_up(int i) {
  23.     int p = i / 2;
  24.     if(vec[p] > vec[i]) {
  25.         std::swap(vec[i], vec[p]);
  26.         sift_up(p);
  27.     } else {
  28.         return;
  29.     }
  30. }
  31.  
  32. void sift_down(int i) {
  33.     int ch1, ch2;
  34.     ch1 = i*2+1;
  35.     ch2 = i*2+2;
  36.     if(ch1 > vec.size()-1) return;
  37.     if(ch1 == vec.size()-1) ch2 = ch1;
  38.     int im = vec[ch1] < vec[ch2] ? ch1 : ch2;
  39.     if(vec[im] < vec[i]) {
  40.         std::swap(vec[im], vec[i]);
  41.         sift_down(im);
  42.     } else {
  43.         return;
  44.     }
  45. }
  46.  
  47. int pop(){
  48.     int head = vec[0];
  49.     vec[0] = vec.back();
  50.     vec.pop_back();
  51.     sift_down(0);
  52.     return head;
  53. }
  54.  
  55. int main()
  56. {
  57.  
  58.     int n;
  59.     std::cin >> n;
  60.     int tmp;
  61.     for(int i = 0; i < n;i++){
  62.         std::cin >> tmp;
  63.         push(tmp);
  64.     }
  65.    
  66.     int tmp1;
  67.     int tmp2;
  68.     int tmp3;
  69.    
  70.     while(vec.size() > 1) {
  71.         tmp1 = pop();
  72.         tmp2 = pop();
  73.         tmp3 = tmp1 + tmp2;
  74.         sum += tmp3/20.0;
  75.         push(tmp3);
  76.     }
  77.  
  78.     std::cout << std::fixed << std::setprecision(2) << sum << std::endl;
  79. }
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement