Submission #65031584

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def li():
    return list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
n,x=li()
scp=[li() for _ in range(n)]
dp={}
rr=[0]*(1<<n)
for i in range(1<<n):
    tmp=0
    for j in range(n):
        if (i>>j)&1:
            tmp+=scp[j][0]
    rr[i]=tmp
    
def solve(state,val):
    if (state,val) in dp:return dp[(state,val)]
    res=rr[state]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

def li():
    return list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**6)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

n,x=li()
scp=[li() for _ in range(n)]
dp={}
rr=[0]*(1<<n)
for i in range(1<<n):
    tmp=0
    for j in range(n):
        if (i>>j)&1:
            tmp+=scp[j][0]
    rr[i]=tmp
    
def solve(state,val):
    if (state,val) in dp:return dp[(state,val)]
    res=rr[state]
    for i in range(n):
        if (state>>i)&1:
            continue
        if val-scp[i][1]<0:continue
        nxt=state+(1<<i)
        tmp=(scp[i][2]/100)*solve(nxt,val-scp[i][1])+(1-scp[i][2]/100)*solve(state,val-scp[i][1])
        res=max(res,tmp)
    dp[(state,val)]=res
    return res
print(solve(0,x))

Submission Info

Judge Result