結果
問題 | No.2390 Udon Coupon (Hard) |
ユーザー |
![]() |
提出日時 | 2023-07-21 23:19:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 252 ms / 2,000 ms |
コード長 | 1,330 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 146,304 KB |
最終ジャッジ日時 | 2024-10-06 01:57:13 |
合計ジャッジ時間 | 8,883 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
#############################################################import syssys.setrecursionlimit(10**7)from heapq import heappop,heappushfrom collections import deque,defaultdict,Counterfrom bisect import bisect_left, bisect_rightfrom itertools import product,combinations,permutationsipt = sys.stdin.readlinedef iin():return int(ipt())def lmin():return list(map(int,ipt().split()))MOD = 998244353inf = 1<<60#############################################################M = 3000**2N = iin()A1,B1 = lmin()A2,B2 = lmin()A3,B3 = lmin()if N < M:dp = [-inf]*(N+1)dp[0] = 0for i in range(1,N+1):if i >= A1:dp[i] = max(dp[i],dp[i-A1]+B1)if i >= A2:dp[i] = max(dp[i],dp[i-A2]+B2)if i >= A3:dp[i] = max(dp[i],dp[i-A3]+B3)print(max(dp))else:L = N-Mr = (L+A1-1)//A1t = r*A1dp = [-inf]*(M+1)dp[t-L] = max(dp[t-L],B1*r)r = (L+A2-1)//A2t = r*A2dp[t-L] = max(dp[t-L],B2*r)r = (L+A3-1)//A3t = r*A3dp[t-L] = max(dp[t-L],B3*r)for i in range(1,M+1):if i >= A1:dp[i] = max(dp[i],dp[i-A1]+B1)if i >= A2:dp[i] = max(dp[i],dp[i-A2]+B2)if i >= A3:dp[i] = max(dp[i],dp[i-A3]+B3)print(max(dp))