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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MIN_INF = -(1ll<<61);

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    srand(1000003);
    int n; ll m;
    cin >> n >> m;
    vector <ll> A(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    set <ll> S;


    if (m <= 2500000 && n * m <= 100000000) {
        for (ll i = 0; i <= m; i++) {
            S.insert(i);
        }
    }
    else {
        S.insert(0);
        int max_bits = 1;
        while ((1ll<<max_bits) <= m) {
            max_bits++;
        }
        //max_bits--;
        int max_numb = max(128 * n, n * n / 4 + 10);
        vector <string> Str;
        /*while (bits_num <= max_bits) {
            int cur = 0;
            Str.clear();
            string s = "";
            for (int i = 0; i < bits_num; i++) {
                s.push_back('1');
            }
            for (int i = 0; i < max_bits - bits_num; i++) {
                s.push_back('0');
            }
            reverse(s.begin(), s.end());
            do {
                long long val = strtoll(s.c_str(), nullptr, 2);
                Str.push_back(s);                
                //cout << bits_num << "  " << s << " " << val << " | " << (val > m) <<endl;
                if (val > m) {
                    break;
                }
                S.insert(val);
                cur++;
            }
            while (next_permutation(s.begin(), s.end()));
            //cout << s <<endl;
            bits_num++;
            if (cur >= max_numb) {
                break;
            }
        }

        if (bits_num < max_bits) {
            //cout << "Second part" <<endl;
            while (bits_num < max_bits) {
                int cur = 0;
                
                for (size_t j = 0; j < Str.size(); j++) {
                    string &s = Str[j];
                    int i = max_bits - 1;
                    while (i >= 0 && s[i] == '1') {
                        i--;
                    }
                    if (i < 0) {
                        continue;
                    }
                    s[i] = '1';
                    if (j > 0 && s == Str[j-1]) {
                        next_permutation(s.begin(), s.end());
                    }
                    long long val = strtoll(s.c_str(), nullptr, 2);
                    //cout << bits_num << "  " << s << " " << val << " | " << (val > m) <<endl;
                    if (val > m) {
                        continue;
                    }
                    S.insert(val);
                    cur++;
                }

                bits_num++;
            }
        }*/

        for (ll i = m; i > m-107025 && i >= m-i; i--) {
            S.insert(i);
            S.insert(m-i);
            S.insert((i*i) % (m+1));
            S.insert(abs(1ll * rand() * rand()) % (m+1));
            S.insert(abs(1ll * rand() * rand() * rand()) % (m+1));
        }
        
        {
            int b = 1;
            string s = "";
            for (int i = 0; i < b; i++) {
                s.push_back('1');
            }
            for (int i = 0; i < max_bits - b; i++) {
                s.push_back('0');
            }
            do {
                long long val = strtoll(s.c_str(), nullptr, 2);
                //cout << bits_num << "  " << s << " " << val << " | " << (val > m) <<endl;
                if (val <= m) {
                    S.insert(val);
                }
                else {
                    break;
                }
            }
            while (next_permutation(s.begin(), s.end()));
        }
        for (int b = 2; b < max_bits; b++) {
            string s = "";
            for (int i = 0; i < b; i++) {
                s.push_back('1');
            }
            for (int i = 0; i < max_bits - b; i++) {
                s.push_back('0');
            }
            for (int it = 0; it < max_numb; it++) {
                long long val = strtoll(s.c_str(), nullptr, 2);
                //cout << bits_num << "  " << s << " " << val << " | " << (val > m) <<endl;
                if (val <= m) {
                    S.insert(val);
                }
                random_shuffle(s.begin(), s.end());
            }
        }
    }

    vector <ll> B;
    for (ll i : S) {
        int bits = 0;
        for (int j = 0; j < 60; j++) {
            if (i & (1ll<<j)) {
                bits++;
            }
        }
        // cout << "B " << i << " " << bits <<endl;
        B.push_back(bits);
    }

    int k = B.size();
    vector < vector <ll> > D(2, vector <ll> (k+1, 0));
    for (int i = 1; i <= n; i++) {
        int i0 = i % 2, i1 = (i-1) % 2;
        for (int j = 0; j < i; j++) {
            D[i0][j] = MIN_INF;
        }
        for (int j = i; j <= k; j++) {
            D[i0][j] = D[i0][j-1];
            if (D[i1][j-1] != MIN_INF && D[i0][j] < D[i1][j-1] + B[j-1] * A[i]) {
                D[i0][j] = D[i1][j-1] + B[j-1] * A[i];
            }
            /*
            if (D[i0][j] != MIN_INF) {
                cout << i << " " << j << " " << D[i0][j] <<endl;
            }
            */
        }
    }
    cout << D[n % 2][k] <<endl;
    return 0;
}