fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. //必要があれば，関数をいくつでも追加して良い
  5. #define MAXN 200005
  6. static int heap[MAXN];
  7. static int hn;
  8.  
  9. static void push(int x){
  10.     int i = hn++;
  11.     heap[i] = x;
  12.     while(i > 0){
  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.     int ret = heap[0];
  22.     int i = 0;
  23.     heap[0] = heap[--hn];
  24.     while(1){
  25.         int l = 2*i+1, r = 2*i+2, m = i;
  26.         if(l < hn && heap[l] > heap[m]) m = l;
  27.         if(r < hn && heap[r] > heap[m]) m = r;
  28.         if(m == i) break;
  29.         int t = heap[m]; heap[m] = heap[i]; heap[i] = t;
  30.         i = m;
  31.     }
  32.     return ret;
  33. }
  34.  
  35. int solve(){
  36.     int ret;
  37.     //ここにプログラムを書く
  38.     //ret に答えを入れてメイン関数に返す
  39.     int n, q, i, x;
  40.     scanf("%d %d", &n, &q);
  41.     hn = 0;
  42.     for(i = 0; i < n; i++){
  43.         scanf("%d", &x);
  44.         push(x);
  45.     }
  46.     for(i = 0; i < q; i++){
  47.         if(heap[0] == 0) break;
  48.         x = pop();
  49.         push(x/2);
  50.     }
  51.     ret = 0;
  52.     for(i = 0; i < hn; i++) ret += heap[i];
  53.     return ret;
  54. }
  55.  
  56. //メイン関数はいじらなくて良い
  57. int main(void){
  58.     printf("%d\n",solve());
  59.     return 0;
  60. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
7 2
10 40 60 30 80 5 30
stdout
copy 
185
https://ideone.com/gEgvlJ
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!