結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2021-05-05 02:24:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,479 ms / 2,000 ms |
コード長 | 761 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 184,108 KB |
最終ジャッジ日時 | 2024-07-23 21:50:08 |
合計ジャッジ時間 | 49,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
def dfs(t,m,v,w):global ansif t==w:L.append([m,v])returndfs(t+1,m+a[t],v,w)if t+1 < w: dfs(t+2,m-c[t+1],v+b[t+1],w)def solve(x,y):x.sort(key=f)y.sort(key=f)for i in range(len(x)-1)[::-1]:if x[i][1] < x[i+1][1]: x[i][1] = x[i+1][1]ans = idx = 0L = len(x)for m,v in y[::-1]:while idx < L and x[idx][0] + m < 0:idx += 1if idx < L:ans = max(ans,x[idx][1]+v)return answ = int(input())a,b,c = [0]*w, [0]*w, [0]*wfor i in range(w):a[i],b[i],c[i] = map(int,input().split())ans = 0for W in [w//2,w//2+1]:f = lambda x:x[0]L = x = []dfs(0,0,0,W)L = y = []dfs(W,0,0,w)ans = max(ans,solve(x,y))print(ans)