fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAXN 100010
  5.  
  6. int heap[MAXN];
  7. int sz = 0;
  8.  
  9. void swap(int *x, int *y){
  10.     int tmp = *x;
  11.     *x = *y;
  12.     *y = tmp;
  13. }
  14.  
  15. void push(int x){
  16.     heap[++sz] = x;
  17.     int i = sz;
  18.     while(i > 1 && heap[i] > heap[i/2]){
  19.         swap(&heap[i], &heap[i/2]);
  20.         i /= 2;
  21.     }
  22. }
  23.  
  24. int pop(){
  25.     if(sz == 0) return 0;
  26.     int ret = heap[1];
  27.     heap[1] = heap[sz--];
  28.  
  29.     int i = 1;
  30.     while(1){
  31.         int left = i * 2;
  32.         int right = i * 2 + 1;
  33.         int largest = i;
  34.  
  35.         if(left <= sz && heap[left] > heap[largest]) largest = left;
  36.         if(right <= sz && heap[right] > heap[largest]) largest = right;
  37.  
  38.         if(largest == i) break;
  39.  
  40.         swap(&heap[i], &heap[largest]);
  41.         i = largest;
  42.     }
  43.  
  44.     return ret;
  45. }
  46.  
  47. int solve(){
  48.     int n, q;
  49.     scanf("%d %d", &n, &q);
  50.  
  51.     for(int i = 0; i < n; i++){
  52.         int d;
  53.         scanf("%d", &d);
  54.         push(d);
  55.     }
  56.  
  57.     for(int i = 0; i < q; i++){
  58.         int top = pop();
  59.         top /= 2;
  60.         if(top > 0) push(top);
  61.     }
  62.  
  63.     int ret = 0;
  64.     for(int i = 1; i <= sz; i++){
  65.         ret += heap[i];
  66.     }
  67.  
  68.     return ret;
  69. }
  70.  
  71. int main(void){
  72.     printf("%d\n", solve());
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
7 2
10 40 60 30 80 5 30
stdout
copy 
185
https://ideone.com/6f99Nm
language:
C (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!