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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,LL> PLL;
typedef vector<PIL> VPIL;
typedef vector<PLL> VPLL;
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define ALL(c) (c).begin(),(c).end()
#define FOREACH(it,c,i) for(auto it=(c).begin()+(i);it!=(c).end();++it)
#define SIZE(c) (int)(c).size()
LL mx=0,ps,pst,m,a[201],yet[202];
int tc[65536]={},bt=0,n,i,j,h;
int C(ULL a)
{
    int r=0;
    while(a)
    {
        r+=tc[a&65535];
        a>>=16;
    }
    return r;
}
int main()
{
    for(i=1;i<65536;i<<=1)
            for(j=i;j<2*i;++j)
                tc[j]=tc[j-i]+1;
    scanf("%d%lld",&n,&m);
    for(i=0;i<n;++i){
        scanf("%lld",a+i);
    }
    VPLL t1,t2;
    t1.PB(MP(-1,0));
    for(i=0;i<n;++i){
       t1.PB(MP(m,0));
        if(a[i]>0)
            FOREACH(it,t1,1){
                auto p=*(it-1);
                pst=p.ST+1;
                bt=C(pst);
                for(;pst<=it->ST;pst=(pst|(pst+1)),bt++)
                    t2.PB(MP(pst,p.ND+bt*a[i]));
            }
        else{
            FOREACH(it,t1,1){
                auto p=*(it-1);
                pst=p.ST+1;
                while(pst<=it->ST){
                    t2.PB(MP(pst,p.ND+C(pst)*a[i]));
                    pst&=pst-1;
                    pst=pst+pst-(pst&(pst-1));
                    if(pst==0)
                        break;
                }
                ps=p.ST;
            }
        }
        j=1;
        for(h=1;h<SIZE(t2);++h)
            if(t2[h].ND>t2[j-1].ND){
                t2[j]=t2[h];
                ++j;
            }
        t2.resize(j);
//        for(auto p:t2)
//            printf("%lld %lld\n",p.ST,p.ND);
//        printf("\n");
        t2.swap(t1);
        t2.clear();
    }
    printf("%lld\n",t1.back().ND);
}