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
#include <stdio.h>
#include <limits.h>

long long A[200];
long long a_len;

long long b_total_limit;

long long oblicz(int a_index, unsigned long long min_b);
unsigned long long next_higher_b(unsigned long long b);
unsigned long long next_lower_b(unsigned long long b);
long long number_of_bits(unsigned long long b);

int main()
{
	scanf("%lld %lld", &a_len, &b_total_limit);
	
	for (long long i = 0LL; i < a_len; i++) {
		scanf("%lld", &A[i]);
	}

	long long wynik = oblicz(0, 0LL);

	printf("%lld\n", wynik);
}

long long oblicz(int a_index, unsigned long long min_b)
{
	unsigned long long max_b = b_total_limit - a_len + a_index + 1ULL;
	
	if (A[a_index] != 0LL)
	{
		unsigned long long b = min_b;
		long long max = LLONG_MIN;
		
		while (b <= max_b) {
			long long res = A[a_index] * number_of_bits(b);
			if (a_index < a_len - 1) {
				res += oblicz(a_index + 1, b + 1ULL);
			}
			if (res > max) {
				max = res;
			}

			if (A[a_index] > 0LL) {
				b = next_higher_b(b);
			} else {
				b = next_lower_b(b);
			}
		}
		
		return max;
	}
	else
	{
		if (a_index == a_len - 1) {
			return 0LL;
		} else {
			return oblicz(a_index + 1, min_b + 1LL);
		}
	}
}

unsigned long long next_higher_b(unsigned long long b)
{
	for (int i = 0; i < 64; i++) {
		if ((b & (1LL << i)) == 0) {
			return b + (1LL << i);
		}
	}

	return b_total_limit + 1LL;
}

unsigned long long next_lower_b(unsigned long long b)
{
	int first_bit_one = -1;
	for (int i = 0; i < 64; i++) {
		if ((b & (1ULL << i)) != 0) {
			first_bit_one = i;
			break;
		}
	}
	
	if (first_bit_one == -1) {
		return b_total_limit + 1ULL;
	}
	
	int second_bit_one = -1;
	for (int i = first_bit_one + 1; i < 64; i++) {
		if ((b & (1ULL << i)) != 0) {
			second_bit_one = i;
			break;
		}
	}

	if (second_bit_one == -1) {
		return b_total_limit + 1ULL;
	}
	
	for (int i = first_bit_one; i < second_bit_one; i++) {
		b += (1ULL << i);
	}
	
	return b;
}

long long number_of_bits(unsigned long long b)
{
	long long res = 0LL;
	
	for (int i = 0; i < 64; i++) {
		if ((b & (1ULL << i)) != 0) {
			res++;
		}
	}
	
	return res;
}