#include <iostream> int aa[200]; int bb[200]; int wzmocnienie (int b) { int c = 0; while(b > 0) { c += b%2; b /= 2; } return c; } int mini(int first, int last) { int mini = aa[first]; int place = first; for(int i = first; i <=last; i++) { if (aa[i] < mini) { mini = aa[i]; place = i; } } return place; } int maxi(int first, int last) { int maxi = aa[first]; int place = first; for(int i = first; i <=last; i++) { if (aa[i] > maxi) { maxi = aa[i]; place = i; } } return place; } int best_place(int first, int last) { int place = first; int b = wzmocnienie(place); int b_i; for(int i = first; i <=last; i++) { b_i = wzmocnienie(i); if(b_i <= b) { b = b_i; place = i; } } return place; } int best_place_max(int first, int last) { int place = first; int b = wzmocnienie(place); int b_i; for(int i = first; i <=last; i++) { b_i = wzmocnienie(i); if(b_i >= b) { b = b_i; place = i; } } return place; } void minimize (int first, int last, int a0, int ax) { int a_min = mini(a0,ax); int partition; if (aa[a_min] > 0) { a_min = maxi(a0,ax); partition = best_place_max(first + a_min -a0, last - ax + a_min); } else { partition = best_place(first + a_min - a0, last - ax + a_min); } bb[a_min] = wzmocnienie(partition); if(a0 != a_min) { minimize(first, partition - 1, a0, a_min - 1); } if(ax != a_min){ minimize(partition + 1, last, a_min +1, ax); } } int main() { int n, m; std::cin >> n >> m; int jakosc = 0; for(int i = 0; i < 200; i++) { aa[i] = 0; bb[i] = 0; } for(int i = 0; i < n; i++) { std::cin >> aa[i]; bb[i] = wzmocnienie(i); } minimize(0,m,0,n-1); for(int j = n-1; j >= 0; j--) { jakosc += bb[j] * aa[j]; } std::cout << jakosc; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <iostream> int aa[200]; int bb[200]; int wzmocnienie (int b) { int c = 0; while(b > 0) { c += b%2; b /= 2; } return c; } int mini(int first, int last) { int mini = aa[first]; int place = first; for(int i = first; i <=last; i++) { if (aa[i] < mini) { mini = aa[i]; place = i; } } return place; } int maxi(int first, int last) { int maxi = aa[first]; int place = first; for(int i = first; i <=last; i++) { if (aa[i] > maxi) { maxi = aa[i]; place = i; } } return place; } int best_place(int first, int last) { int place = first; int b = wzmocnienie(place); int b_i; for(int i = first; i <=last; i++) { b_i = wzmocnienie(i); if(b_i <= b) { b = b_i; place = i; } } return place; } int best_place_max(int first, int last) { int place = first; int b = wzmocnienie(place); int b_i; for(int i = first; i <=last; i++) { b_i = wzmocnienie(i); if(b_i >= b) { b = b_i; place = i; } } return place; } void minimize (int first, int last, int a0, int ax) { int a_min = mini(a0,ax); int partition; if (aa[a_min] > 0) { a_min = maxi(a0,ax); partition = best_place_max(first + a_min -a0, last - ax + a_min); } else { partition = best_place(first + a_min - a0, last - ax + a_min); } bb[a_min] = wzmocnienie(partition); if(a0 != a_min) { minimize(first, partition - 1, a0, a_min - 1); } if(ax != a_min){ minimize(partition + 1, last, a_min +1, ax); } } int main() { int n, m; std::cin >> n >> m; int jakosc = 0; for(int i = 0; i < 200; i++) { aa[i] = 0; bb[i] = 0; } for(int i = 0; i < n; i++) { std::cin >> aa[i]; bb[i] = wzmocnienie(i); } minimize(0,m,0,n-1); for(int j = n-1; j >= 0; j--) { jakosc += bb[j] * aa[j]; } std::cout << jakosc; return 0; } |