Submission #8522115
Source Code Expand
N,W=map(int,input().split()) wv=[list(map(int,input().split())) for _ in range(N)] w1=wv[0][0] wm=max([i[0] for i in wv]) Wlist=[0]+[j*(w1+i) for j in range(1,N+1) for i in range(4)] dp=[[0]*(4*N+1) for _ in range(N+1)] #dp[i][j]:N個の物に対して強度(Wlist[j])のバッグ for i in range(1,N+1): w,v=wv[i-1] for j in range(4*N+1): if w<=Wlist[j]: ind=0 d=float("inf") for k in range(4*N+1): if (Wlist[j]-w)>=Wlist[k] and (Wlist[j]-w)-Wlist[k]<d: d=(Wlist[j]-w)-Wlist[k] ind=k dp[i][j]=max(dp[i-1][j],dp[i-1][ind]+v) else: dp[i][j]=dp[i-1][j] ind=0 d=float("inf") for k in range(4*N+1): if W>=Wlist[k] and W-Wlist[k]<d: d=W-Wlist[k] ind=k print(dp[N][ind])
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | Wattawa |
Language | Python (3.4.3) |
Score | 0 |
Code Size | 791 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 3820 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3 |
All | antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
antigreedy0 | TLE | 2104 ms | 3744 KB |
antigreedy1 | TLE | 2104 ms | 3820 KB |
antigreedy2 | TLE | 2104 ms | 3812 KB |
example0 | AC | 18 ms | 3064 KB |
example1 | AC | 18 ms | 3064 KB |
example2 | AC | 18 ms | 3064 KB |
example3 | AC | 18 ms | 3064 KB |
quarter0 | TLE | 2104 ms | 3816 KB |
quarter1 | TLE | 2104 ms | 3816 KB |
quarter2 | TLE | 2104 ms | 3820 KB |
rand0 | AC | 19 ms | 3064 KB |
rand1 | AC | 724 ms | 3304 KB |
rand2 | AC | 117 ms | 3064 KB |
smallw0 | TLE | 2104 ms | 3808 KB |
smallw1 | TLE | 2104 ms | 3812 KB |
smallw2 | TLE | 2104 ms | 3816 KB |