fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. static int *heap;
  5. static int hn;
  6.  
  7. static void push(int x)
  8. {
  9.     int i = hn++;
  10.     heap[i] = x;
  11.     while(i > 0)
  12. 	{
  13.         int p = (i-1)/2;
  14.         if(heap[p] >= heap[i]) break;
  15.         int t = heap[p]; heap[p] = heap[i]; heap[i] = t;
  16.         i = p;
  17.     }
  18. }
  19.  
  20. static int pop(void)
  21. {
  22.     int ret = heap[0];
  23.     int i = 0;
  24.     heap[0] = heap[--hn];
  25.     while(1)
  26. 	{
  27.         int l = 2*i+1, r = 2*i+2, m = i;
  28.         if(l < hn && heap[l] > heap[m]) m = l;
  29.         if(r < hn && heap[r] > heap[m]) m = r;
  30.         if(m == i) break;
  31.         int t = heap[m]; heap[m] = heap[i]; heap[i] = t;
  32.         i = m;
  33.     }
  34.     return ret;
  35. }
  36.  
  37. int solve()
  38. {
  39.     int ret;
  40.     int n, q, i, x;
  41.     scanf("%d %d", &n, &q);
  42.     heap = (int *)malloc(sizeof(int) * n);
  43.     hn = 0;
  44.     for(i = 0; i < n; i++)
  45. 	{
  46.         scanf("%d", &x);
  47.         push(x);
  48.     }
  49.     for(i = 0; i < q; i++)
  50. 	{
  51.         if(heap[0] == 0) break;
  52.         x = pop();
  53.         push(x/2);
  54.     }
  55.     ret = 0;
  56.     for(i = 0; i < hn; i++) ret += heap[i];
  57.     free(heap);
  58.     return ret;
  59. }
  60.  
  61.  
  62. int main(void)
  63. {
  64.     printf("%d\n",solve());
  65.     return 0;
  66. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
7 2
10 40 60 30 80 5 30
stdout
copy 
185
https://ideone.com/FuXs1W
language:
C (gcc 8.3)
created:
3 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!