結果
問題 | 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 sys sys.setrecursionlimit(10**7) from heapq import heappop,heappush from collections import deque,defaultdict,Counter from bisect import bisect_left, bisect_right from itertools import product,combinations,permutations ipt = sys.stdin.readline def iin(): return int(ipt()) def lmin(): return list(map(int,ipt().split())) MOD = 998244353 inf = 1<<60 ############################################################# M = 3000**2 N = iin() A1,B1 = lmin() A2,B2 = lmin() A3,B3 = lmin() if N < M: dp = [-inf]*(N+1) dp[0] = 0 for 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-M r = (L+A1-1)//A1 t = r*A1 dp = [-inf]*(M+1) dp[t-L] = max(dp[t-L],B1*r) r = (L+A2-1)//A2 t = r*A2 dp[t-L] = max(dp[t-L],B2*r) r = (L+A3-1)//A3 t = r*A3 dp[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))