結果
問題 | No.2434 RAKUTAN de RAKUTAN |
ユーザー |
|
提出日時 | 2023-08-18 23:47:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,004 ms / 2,000 ms |
コード長 | 2,425 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,008 KB |
実行使用メモリ | 304,156 KB |
最終ジャッジ日時 | 2024-11-28 11:26:37 |
合計ジャッジ時間 | 8,639 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import *input = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())class SegmentTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numself.size = nfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):k += self.numself.tree[k] = self.segfunc(self.tree[k],x)while k > 1:k >>= 1self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])def query(self, l, r):if r==self.size:r = self.numres = self.ide_elel += self.numr += self.numright = []while l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:right.append(self.tree[r-1])l >>= 1r >>= 1for e in right[::-1]:res = self.segfunc(res,e)return resN,H,X = mi()G = int(input())G = li()B = int(input())B = li()day = set([0,N])for i in range(X+1):day.add(i)for i in range(X+1):if 0 <= N-i:day.add(N-i)for g in G:for i in range(-X,X+1):if 0 <= g+i <= N:day.add(g+i)for b in B:for i in range(-X,X+1):if 0 <= b+i <= N:day.add(b+i)day = sorted(day)d_to_i = {d:i for i,d in enumerate(day)}n = len(day)M = max(len(G),len(B))INF = H + 1dp = [[INF]*(2*M+1) for i in range(n)]dp[0][0] = 0G = set(G)B = set(B)for i in range(1,n):d = day[i]p = 0if d in G:p = 1elif d in B:p = -1for h in range(-M,M+1):if dp[i-1][h] == INF:continuedp[i][h+p] = min(dp[i][h+p],dp[i-1][h])if d-X in d_to_i:pre = d_to_i[d-X]for h in range(-M,M+1):if dp[pre][h] == INF:continuedp[i][h+p] = min(dp[i][h+p],dp[pre][h]+1)for tani in range(-M,M+1)[::-1]:if dp[-1][tani] <= H:print(tani)break