Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- typedef unsigned long long ull;
- std::vector <int> vec;
- long double sum = 0.0;
- void sift_up(int i);
- void sift_down(int i);
- void push(int tmp) {
- vec.push_back(tmp);
- int size = (int)(vec.size())-1;
- sift_up(size);
- }
- void sift_up(int i) {
- int p = i / 2;
- if(vec[p] > vec[i]) {
- std::swap(vec[i], vec[p]);
- sift_up(p);
- } else {
- return;
- }
- }
- void sift_down(int i) {
- int ch1, ch2;
- ch1 = i*2+1;
- ch2 = i*2+2;
- if(ch1 > vec.size()-1) return;
- if(ch1 == vec.size()-1) ch2 = ch1;
- int im = vec[ch1] < vec[ch2] ? ch1 : ch2;
- if(vec[im] < vec[i]) {
- std::swap(vec[im], vec[i]);
- sift_down(im);
- } else {
- return;
- }
- }
- int pop(){
- int head = vec[0];
- vec[0] = vec.back();
- vec.pop_back();
- sift_down(0);
- return head;
- }
- int main()
- {
- int n;
- std::cin >> n;
- int tmp;
- for(int i = 0; i < n;i++){
- std::cin >> tmp;
- push(tmp);
- }
- int tmp1;
- int tmp2;
- int tmp3;
- while(vec.size() > 1) {
- tmp1 = pop();
- tmp2 = pop();
- tmp3 = tmp1 + tmp2;
- sum += tmp3/20.0;
- push(tmp3);
- }
- std::cout << std::fixed << std::setprecision(2) << sum << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement