Submission #67003678

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T=int(input())
for _ in range(T):
    N,W=map(int, input().split())
    bit=[[] for _ in range(60)]
    for i in range(N):
        x,y=map(int, input().split())
        bit[x].append(y)
    px=[]
    sz=[]
    for i in range(60):
        a=sorted(bit[i],reverse=True)
        ps=[0]
        for v in a:
            ps.append(ps[-1]+v)
        px.append(ps)
        sz.append(len(a))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

T=int(input())

for _ in range(T):
    N,W=map(int, input().split())
    bit=[[] for _ in range(60)]
    for i in range(N):
        x,y=map(int, input().split())
        bit[x].append(y)

    px=[]
    sz=[]
    for i in range(60):
        a=sorted(bit[i],reverse=True)
        ps=[0]
        for v in a:
            ps.append(ps[-1]+v)
        px.append(ps)
        sz.append(len(a))

    dp={0:0}

    for i in range(59,-1,-1):
        msk=(W>>i)&1
        sb=sz[i]
        ps=px[i]

        ndp={}
        for c,val in dp.items():
            u=c+msk
            mx=min(u,sb)
            for k in range(mx+1):
                nv=val+ps[k]
                nc=(u-k)*2
                if nc not in ndp or ndp[nc]<nv:
                    ndp[nc]=nv

        dp=ndp
    print((max(dp.values())))

Submission Info

Judge Result