結果
問題 | No.2730 Two Types Luggage |
ユーザー |
![]() |
提出日時 | 2024-05-09 12:46:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,195 ms / 2,000 ms |
コード長 | 1,321 bytes |
コンパイル時間 | 576 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 353,932 KB |
最終ジャッジ日時 | 2024-12-16 01:52:35 |
合計ジャッジ時間 | 25,031 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
from heapq import heappush, heappop, heapifyimport sysfrom collections import defaultdict, deque,Counterfrom math import ceil, floor, sqrt, factorial,gcdfrom itertools import permutations, combinations,productfrom bisect import bisect_left, bisect_rightfrom copy import deepcopyfrom functools import lru_cache #@lru_cache(maxsize=None)from fractions import Fractionfrom copy import deepcopysys.setrecursionlimit(10**6)# input = sys.stdin.readlinevector1 = [[0, -1], [1, 0], [0, 1], [-1, 0]]vector2 = [[0, 1], [1, 0], [-1, 0], [0, -1],[1,-1], [-1, 1], [1, 1], [-1, -1]]def main():N,M,W = map(int,input().split())A = list(map(int,input().split()))B = list(map(int,input().split()))C = list(map(int,input().split()))A.sort(reverse = True)dp = defaultdict(int)dp[0] = 0for i in range(M):ndp = defaultdict(int)for key in dp.keys():ndp[key] = dp[key]if key + B[i] <= W:ndp[key + B[i]] = dp[key] + C[i]dp = ndp#print(dp,ndp)s = [0]for a in A:s.append(s[-1] + a)ans = 0for key in dp.keys():space = W - keyans = max(dp[key]+s[min(space,N)],ans)print(ans)if __name__ == '__main__':main()