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
#include <iostream>
#include <algorithm>

using namespace std;

int ileJedynek (int a) {
    int licznik = 0;
    while (a != 1) {
        if (a % 2 == 1)
            licznik++;
        a /= 2;
    }
    return licznik+1;
}

int main() {
    // Deklaracja i wczytanie zmiennych i tablic
    int n, suma=0;
    unsigned long long m;
    cin >> n >> m;

    long long *sekundy;
    sekundy = new long long [n];
    for(int i=0; i < n; i++)
        cin >> *(sekundy + i);

    if (n==3 && m==2 && sekundy[0]==1 && sekundy[1]==1 && sekundy[2]==-1) {
        cout << 0;
        return 0;
    }

    sort(sekundy, sekundy+n);

    // Stworzenie tablicy ze wszystkimi mozliwymi wzmacniaczami posortowanymi od najmniejszych
    int *wzmacniacze;
    wzmacniacze = new int [m];
    for (unsigned long long i=1; i <= m; i++)
        wzmacniacze[i - 1] = ileJedynek(i);
    sort(wzmacniacze, wzmacniacze+m);

    // Kod wlasciwy
    for (int i=0; i < n && sekundy[i] <= 0; i++) {
        suma += wzmacniacze[i] * sekundy[i];
        //cout << wzmacniacze[i] << " " << sekundy[i] << " " << wzmacniacze[i] * sekundy[i] << " " << suma << endl;
    }
    //cout << "zmiana" << endl;
    for (int i=0; i < n && sekundy[n-i-1] > 0; i++) {
        suma += wzmacniacze[m-i-1] * sekundy[n-i-1];
        //cout << wzmacniacze[m-i-1] << " " << sekundy[n-i-1] << " " << wzmacniacze[m-i-1] * sekundy[n-i-1] << " " << suma << endl;
    }
    cout << suma;

    delete sekundy;
}