fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 100
  5.  
  6. int t[MAX+1]; 
  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 heap_up(int idx){
  16. 	while(idx>1&&t[idx]>t[idx/2]){
  17. 		swap(&t[idx], &t[idx/2]);
  18. 		idx=idx/2;
  19. 	}
  20. }
  21.  
  22. void heap_down(int idx){
  23. 	int max_idx, left, right;
  24. 	max_idx=idx;
  25. 	left=2*idx;
  26. 	right=2*idx+1;
  27.  
  28. 	if(left<=sz && t[left]>t[max_idx]){
  29. 		max_idx=left;
  30. 	}
  31. 	if(right<=sz && t[right]>t[max_idx]){
  32. 		max_idx=right;
  33. 	}
  34. 	if(max_idx!=idx){
  35. 		swap(&t[idx], &t[max_idx]);
  36. 		heap_down(max_idx);
  37. 	}
  38.  
  39. }
  40.  
  41. void insert(int defense){
  42. 	t[++sz]=defense;
  43. 	heap_up(sz);
  44. }
  45.  
  46. int pop_max(){
  47. 	int max_defense=t[1];
  48. 	t[1]=t[sz--];
  49. 	heap_down(1);
  50. 	return max_defense;
  51. }
  52.  
  53. int solve(){
  54.     int ret=0;
  55.     int i, n, q, d_i;
  56.     scanf("%d %d", &n, &q);
  57.     for(i=1;i<=n;i++){
  58.         scanf("%d",&d_i);
  59.         insert(d_i);
  60.     }
  61.  
  62.     for(i=0; i<q; i++){
  63.     	int max_defense=pop_max();
  64.     	 int reduced_defense=max_defense/2;
  65.     	 insert(reduced_defense);
  66.     }
  67.  
  68.     for(i=1; i<=sz; i++){
  69.     	ret+=t[i];
  70.     }
  71.  
  72. 	return ret;
  73. }
  74.  
  75. //メイン関数はいじらなくて良い
  76. int main(void){
  77.     printf("%d\n",solve());
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
7 2
10 40 60 30 80 5 30
stdout
copy 
185
https://ideone.com/bHb0qX
language:
C (gcc 8.3)
created:
2 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!