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
#include <bits/stdc++.h>
#pragma GCC optimize "03"

using namespace std;

int n, a, b, c;
long long m;
long long pot[70];
long long t[201];
long long s[201];
long long dp[70][201][201];
long long roz[10001][201];

int main()
{
	scanf("%d%lld", &n, &m);
	pot[0]=1;
	pot[1]=1;
	a=1;
	while(pot[a]<m)
	{
		++a;
		pot[a]=pot[a-1]<<1;
	}
	for(int i=1; i<=n; ++i)
	{
		roz[0][i]=-4000000000000000000ll;
		for(int j=i+1; j<=n; ++j)
		{
			dp[0][i][j]=-4000000000000000000ll;
			dp[1][i][j]=-4000000000000000000ll;
		}
	}
	for(int i=1; i<=n; ++i)
	{
		scanf("%lld", &t[i]);
		s[i]=s[i-1]+t[i];
		dp[0][i][i]=0;
		dp[1][i][i]=t[i];
	}
	for(int g=2; g<=a; ++g)
	{
		for(int i=1; i<=n; ++i)
		{
			for(int j=1; j+i-1<=n; ++j)
			{
				dp[g][j][j+i-1]=-4000000000000000000ll;
				for(int k=0; k<=i; ++k)
				{
					dp[g][j][j+i-1]=max(dp[g][j][j+i-1], dp[g-1][j][j+k-1]+dp[g-1][j+k][j+i-1]+s[j+i-1]-s[j+k-1]);
				}
			}
		}
	}
	a=0;
	b=0;
	c=0;
	++m;
	while(m)
	{
		if(m>=pot[c])
		{
			++a;
			m-=pot[c];
			for(int i=1; i<=n; ++i)
			{
				roz[a][i]=roz[a-1][i];
				for(int j=0; j<=i; ++j)
				{
					roz[a][i]=max(roz[a][i], roz[a-1][j]+dp[c][j+1][i]+(s[i]-s[j])*b);
				}
			}
			++c;
		}
		else
		{
			++b;
			c=0;
		}
	}
	printf("%lld\n", roz[a][n]);
	return 0;
}