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
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int howManyBinaryOnesInNumber(int number){
    int count = 0;
    while(number != 0){
        number = number & (number - 1);
        count++;
    }
    return count;
}

int getBiggestAmountOfOnes(int lastAmount, int maxBits){
    int biggest = lastAmount + 1;
    for (int i = lastAmount + 1; i <= maxBits; i++){
        if(howManyBinaryOnesInNumber(i) > howManyBinaryOnesInNumber(biggest)){
            biggest = i;
        }
    }
    return biggest;
}

int getSmallestAmountOfOnes(int lastAmount, int localMaxBits){
    int smallest = lastAmount + 1;
    for (int i = lastAmount + 1; i <= localMaxBits; i++){
        if(howManyBinaryOnesInNumber(i) < howManyBinaryOnesInNumber(smallest)){
            smallest = i;
        }
    }
    return smallest;
}

int calcMaxQuality(std::vector<int> qualities, int maxBits){
    std::vector<int> newQualities;
    for (int i = 0; i < qualities.size(); i++){
        int localMaxBits = maxBits - (qualities.size() - (i + 1));
        if(i == 0 && qualities[i] < 0){
            newQualities.push_back(0);
        } else if (i == 0 && qualities[i] >= 0){
            newQualities.push_back(getBiggestAmountOfOnes(0, localMaxBits));
        } else if (qualities[i] < 0) {
            newQualities.push_back(getSmallestAmountOfOnes(newQualities[i - 1], localMaxBits));
        } else {
            newQualities.push_back(getBiggestAmountOfOnes(newQualities[i - 1], localMaxBits));
        }
    }

    int calculatedQuality = 0;
    for (int i = 0; i <= newQualities.size(); i++){
        calculatedQuality += qualities[i] * howManyBinaryOnesInNumber(newQualities[i]);
    }

    return calculatedQuality;
}

int main(){

    int howLong, maxBits;
    std::vector<int> qualities;

    cin >> howLong >> maxBits;

    for (int i = 1; i <= howLong; i++){
        int quality;
        cin >> quality;
        qualities.push_back(quality);
    }

    cout << calcMaxQuality(qualities, maxBits);
    
    return 0;
}