結果
問題 | No.2434 RAKUTAN de RAKUTAN |
ユーザー |
|
提出日時 | 2023-08-16 06:33:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 395 ms / 2,000 ms |
コード長 | 1,275 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 172,484 KB |
最終ジャッジ日時 | 2024-11-24 17:35:04 |
合計ジャッジ時間 | 4,681 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")#######################################################################inf = float("inf")n,h,x = na()G = ni()g = na()B = ni()b = na()h = min(h, B)from collections import defaultdictf = defaultdict(int)for i in range(G):f[g[i]] = 1for i in range(B):f[b[i]] = 2for j in range(1, x+1):if b[i] + j <= n and f[b[i] + j] == 0:f[b[i]+j] = 0f[0] = 0if f[n] == 0:f[n] = 0s = sorted(f)d = {x:i for i, x in enumerate(s)}m = len(s)dp = [[-inf]*(h + 1) for i in range(m)]dp[0][h] = 0from bisect import bisect_right as brfor i in range(1, m):y = s[i]if f[y] == 1:dif = 1elif f[y] == 2:dif = -1else:dif = 0if y - x >= 0:z = br(s, y-x)-1for j in range(h):dp[i][j] = max(dp[i][j], dp[z][j+1]+dif)if y - 1 >= 0:z = br(s, y-1)-1for j in range(h+1):dp[i][j] = max(dp[i][j], dp[z][j]+dif)#print(y, dp[i])print(max(dp[-1]))