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
130
131
132
133
#include <iostream>

using namespace std;
long long a, b, c[202], sumpref[202], pot2[101], dp_max, akt_b, pot, licz_czesci, dp[65][202][202], przed[202][202], dpwyn[64][202][202], wyn[202], max_licz = 1000LL * 1000 * 1000 * 1000 * 1000 * 200;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b;
    for (int i = 0; i < a; i++)
    {
        cin >> c[i];
        sumpref[i + 1] = sumpref[i] + c[i];
    }
    dp_max = 0;
    pot = 1;
    pot2[0] = 1;
    for (int i = 1; i < 64; i++)
    {
        pot2[i] = pot2[i - 1] * 2;
    }
    while (pot <= b)
    {
        dp_max++;
        pot *= 2;
    }
    dp_max--;
    akt_b = b;
    licz_czesci = 0;
    while (akt_b > 0)
    {
       // cout << "zaczynamy od " << b - akt_b << endl
         //    << endl;
        for (int i = 0; i <= dp_max; i++)
        {
            for (int z = 0; z < a; z++)
            {
                for (int x = 0; x < a; x++)
                {
                    dp[i][z][x] = -max_licz;
                    przed[z][x] = -max_licz;
                }
            }
        }
        for (int i = 0; i < a; i++)
        {
            dp[0][i][i] = c[i] * licz_czesci;
            przed[i][i] = max(przed[i][i], dp[0][i][i] + sumpref[i + 1] - sumpref[i]);
        }
        for (int x = 1; x <= dp_max; x++)
        {
            for (int i = 0; i < a; i++)
            {
                for (int z = i; z < a; z++)
                {
                    for (int lacz = i; lacz < z; lacz++)
                    {
                        dp[x][i][z] = max(dp[x][i][z], dp[x - 1][i][lacz] + przed[lacz + 1][z]);
                    }
                    dp[x][i][z] = max(dp[x][i][z], dp[x - 1][i][z]);
                    dp[x][i][z] = max(dp[x][i][z], przed[i][z]);
                }
            }
            for (int i = 0; i < a; i++)
            {
                for (int z = i; z < a; z++)
                {
                    przed[i][z] = max(przed[i][z], dp[x][i][z] + sumpref[z + 1] - sumpref[i]);
                }
            }
        }
        for (int i = 0; i <= dp_max; i++)
        {
        //    cout << "potega dwojki " << i << endl
          //       << endl;
        /*    for (int z = 0; z < a; z++)
            {
                for (int x = 0; x < a; x++)
                {
                    cout << dp[i][z][x] << " ";
                }
*/
            //    cout << endl;
  //          }
            //cout << endl;
        }
        for (int i = 0; i < a; i++)
        {
            for (int z = i; z < a; z++)
            {
                dpwyn[licz_czesci][i][z] = dp[dp_max][i][z];
            }
        }
        licz_czesci++;
        akt_b -= pot2[dp_max];
        if (licz_czesci == 1)
        {
            akt_b++;
        }
        while (dp_max >= 0 && pot2[dp_max] > akt_b)
        {
            dp_max--;
        }
    }
    for (int i = 0; i < a; i++)
    {
        wyn[i] = dpwyn[0][0][i];
    }
    for (int x = 1; x < licz_czesci; x++)
    {

        for (int i = a - 1; i >= 0; i--)
        {
            for (int z = i; z < a; z++)
            {
                if (i == 0)
                {
                    wyn[z] = max(wyn[z], dpwyn[x][i][z]);
                }
                else
                {
         //           cout << i << " " << z << endl;
       //             cout << wyn[i - 1] << " x " << dpwyn[x][i][z] << endl;
                    wyn[z] = max(wyn[z], dpwyn[x][i][z] + wyn[i - 1]);
     //               cout << wyn[i] << endl;
                }
            }
        }
    }
    cout << wyn[a - 1]<<endl;
    return 0;
}