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
124
125
126
127
128
129
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#define mp make_pair
#define zak 210
#define inf 1000000000000000000ll

//#define DBG
#ifdef DBG
	#define debug(...) __VA_ARGS__
#else
	#define debug(...)
#endif

using namespace std;

long long done[zak][zak][70];
long long doneFull[zak][zak][70];

int n;
long long m;
long long sum[zak], fajen[zak];

long long Sum(int p, int k)
{
	return sum[k] - sum[p - 1];
}

int I = 0;

void fill()
{
	for(int i = 0; i < n + 3; i++)
	{
		for(int j = 0; j < n + 3; j++)
		{
			for(int k = 0; k < 70; k++)
			{
				done[i][j][k] = doneFull[i][j][k] = -inf;
			}
		}
	}
}

void Tab(int ile)
{
	for(int i=0;i<ile;i++)printf("    ");
}

long long Ile(int p, int k, long long gr, int tab = 0)
{
	debug(Tab(tab));
	debug(printf("START %d %d %lld\n", p, k, gr));

	if(k - p > gr + 1) return -inf;
	if(k <= p) return 0;
	if(gr == 0) return 0;

	int bits = 63 - __builtin_clzll(gr);
	bool fullBits = gr == (1ll << (bits + 1)) - 1;

	debug(Tab(tab));
	debug(printf("%d %d\n", bits, fullBits ? 1 : 0));

	if(fullBits)
	{
		if(doneFull[p][k][bits] != -inf)
		{
			debug(printf("From fullBits: %lld\n", doneFull[p][k][bits]));
			return doneFull[p][k][bits];
		}
	}
	else
	{
		if(done[p][k][bits] != -inf)
		{
			return done[p][k][bits];
		}
	}

	//k jest PO koncu
	long long best = -inf;

	debug(Tab(tab));
	debug(printf("Prepass\n"));

	for(int i = p; i <= k; ++i)
	{
		//i jest pierwszym który ma najwyższy bit włączony
		long long wyn_left = Ile(p, i, (1ll << bits) - 1, tab + 1);
		long long wyn_right = Sum(i, k - 1) +
			Ile(i, k, gr - (1ll << bits), tab + 1);

		best = max(best, wyn_left + wyn_right);
		debug(Tab(tab));
		debug(printf("For %d-%d (%lld) with i = %d : %lld %lld\n", p,k,gr,i,wyn_left,wyn_right));
	}

	if(fullBits)
	{
		doneFull[p][k][bits] = best;
	}
	else
	{
		done[p][k][bits] = best;
	}

	debug(Tab(tab));
	debug(printf("%d %d %lld RETURNS %lld\n", p, k, gr, best));

	return best;
}

int main()
{

	scanf("%d%lld", &n, &m);
	fill();
	for(int i = 1; i <= n; i++)
	{
		//fajen[i] = 1;
		scanf("%lld", &fajen[i]);
		sum[i] = sum[i - 1] + fajen[i];
	}

	long long wyn = Ile(1, n + 1, m);

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