結果
| 問題 |
No.2686 商品券の使い道
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2024-10-30 01:57:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 378 ms / 3,000 ms |
| コード長 | 4,566 bytes |
| コンパイル時間 | 328 ms |
| コンパイル使用メモリ | 82,312 KB |
| 実行使用メモリ | 98,084 KB |
| 最終ジャッジ日時 | 2024-10-30 01:57:41 |
| 合計ジャッジ時間 | 11,795 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 48 |
ソースコード
## https://yukicoder.me/problems/no/2686
class SegmentTree:
"""
非再帰版セグメント木。
更新は「加法」、取得は「最大値」のもの限定。
"""
def __init__(self, init_array):
n = 1
while n < len(init_array):
n *= 2
self.size = n
self.array = [[] for _ in range(2 * self.size)]
for i, q_array in enumerate(init_array):
self.array[self.size + i] = q_array
end_index = self.size
start_index = end_index // 2
while start_index >= 1:
for i in range(start_index, end_index):
self.array[i] = self._fill(self.array[2 * i], self.array[2 * i + 1])
end_index = start_index
start_index = end_index // 2
def _fill(self, left, right):
q_map = {}
for l, v in left:
q_map[l]= v
for r, v in right:
if r not in q_map:
q_map[r] = 0
q_map[r] = max(v, q_map[r])
q_array = [(q, v) for q, v in q_map.items() ]
q_array.sort(key=lambda x : x[0])
return q_array
def add(self, x, a):
index = self.size + x
self.array[index] += a
while index > 1:
index //= 2
self.array[index] = max(self.array[2 * index], self.array[2 * index + 1])
def find(self, array, q):
if len(array) == 0:
return 0
if array[0][0] > q:
return 0
low = 0
high = len(array) - 1
while high - low > 1:
mid = (high + low) // 2
if array[mid][0] <= q:
low = mid
else:
high = mid
if array[high][0] <= q:
return array[high][1]
else:
return array[low][1]
def get_max(self, l, r, q):
L = self.size + l; R = self.size + r
# 2. 区間[l, r)の最大値を求める
s = 0
while L < R:
if R & 1:
R -= 1
s = max(s, self.find(self.array[R], q))
if L & 1:
s = max(s, self.find(self.array[L], q))
L += 1
L >>= 1; R >>= 1
return s
def solve(N, M, Q, ab):
if N == 1:
A, B = ab[0]
if A <= M and B <= Q:
return A + B
else:
return 0
n1 = N // 2
n2 = N - n1
# n1の全列挙
n1_array = []
for bit3 in range(3 ** n1):
p = 0
q = 0
value = 0
for i in range(n1):
a = bit3 % 3
if a == 1:
p += ab[i][0]
value += ab[i][1]
elif a == 2:
q += ab[i][0]
value += ab[i][1]
bit3 //= 3
if p <= M and q <= Q:
n1_array.append((p, q, value))
# n2の方をseqmenttreeに格納する
p_q_map = {}
for bit3 in range(3 ** n2):
p = 0
q = 0
value = 0
for i in range(n2):
a = bit3 % 3
if a == 1:
p += ab[n1 + i][0]
value += ab[n1 + i][1]
elif a == 2:
q += ab[n1 + i][0]
value += ab[n1 + i][1]
bit3 //= 3
if p <= M and q <= Q:
if p not in p_q_map:
p_q_map[p] = {}
if q not in p_q_map[p]:
p_q_map[p][q] = -1
p_q_map[p][q] = max(p_q_map[p][q], value)
# Pについての座標圧縮
p_set = set()
for p, _, _ in n1_array:
p_set.add(M - p)
for p in p_q_map.keys():
p_set.add(p)
p_list = list(p_set)
p_list.sort()
p_map = {}
for i, p in enumerate(p_list):
p_map[p] = i
# SegmentTree構築s
p_q_array = [[] for _ in range(len(p_list)) ]
for p, q_map in p_q_map.items():
q_array = [ (q, v) for q, v in q_map.items() ]
q_array.sort(key=lambda x: x[0])
p_q_array[p_map[p]] = q_array
# SegmentTree
seg_tree = SegmentTree(p_q_array)
answer= 0
for p, q, v in n1_array:
max_value = seg_tree.get_max(0, p_map[M - p] + 1, Q - q)
ans = v + max_value
answer = max(ans, answer)
return answer
def main():
N, M, Q = map(int, input().split())
ab = []
for _ in range(N):
A, B = map(int, input().split())
ab.append((A, B))
ans = solve(N, M, Q, ab)
print(ans)
if __name__ == "__main__":
main()