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
#include <bits/stdc++.h>

#define BOOST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(a, b, c) for(LL a = b; a < c; ++a)

typedef long long LL;

using namespace std;

map <LL, LL, greater <LL> > stany[206];
LL muzyka[206];

LL find_smaller(LL a, int t, LL bits)
{
    if(t >= bits)
    {
        while(t > bits)
        {
            a ^= (a & -a);
            --t;
        }
        return a;
    }
    
    FOR(i, 0, 62)
    {
        if(t < bits + 1ll && !(a & (1ll << i)))
        {
            ++t;
            a |= (1ll << i);
        }
        else if(t == bits + 1ll && (a & (1ll << i)))
        {
            a ^= (1ll << i);
            break;
        }
    }

    return a;
}

int main()
{
    BOOST;
    LL n, k;
    cin >> n >> k;

    stany[n][0] = k + 1;

    FOR(i, 0, n) cin >> muzyka[i];

    for(LL i = n - 1; i >= 0; --i)
    {
        for(auto& s : stany[i + 1])
        {
            int temp = __builtin_popcountll(s.second - 1);
            LL val = s.first;

            for(LL bit = 0; bit <= 61; bit++)
            {
                if((1ll << bit) >= s.second + 1ll)
                    break;

                LL x = find_smaller(s.second - 1, temp, bit);
                if(x >= i)
                {
                    auto& z = stany[i][val];
                    z = max(z, x);
                }
                val += muzyka[i];
            }
        }

        vector <LL> to_erase;
        LL prev = -1;

        for(auto& s : stany[i])
        {
            if(s.second <= prev)
                to_erase.push_back(s.first);
            else
                prev = s.second;
        }

        for(auto& z : to_erase)
        {
            stany[i].erase(z);
        }
    }

    if(!(stany[0].size()))
        cout << "FATAL ERROR!\n";
    cout << stany[0].begin()->first;
    return 0;
}