結果

問題 No.777 再帰的ケーキ
ユーザー lam6er
提出日時 2025-03-20 20:31:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,461 ms / 2,000 ms
コード長 2,372 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 159,480 KB
最終ジャッジ日時 2025-03-20 20:32:46
合計ジャッジ時間 11,915 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

class SegmentTreeMax:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.size = self.n
        self.tree = [0] * (2 * self.n)
    
    def update(self, idx, value):
        idx += self.n
        if self.tree[idx] >= value:
            return
        self.tree[idx] = value
        while idx > 1:
            idx >>= 1
            new_val = max(self.tree[2*idx], self.tree[2*idx+1])
            if self.tree[idx] == new_val:
                break
            self.tree[idx] = new_val
    
    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n
        while l < r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

# Read input
n = int(input())
cakes = []
all_B = []
for _ in range(n):
    A, B, C = map(int, input().split())
    cakes.append( (A, B, C) )
    all_B.append(B)

# Compress B coordinates
sorted_B = sorted(list(set(all_B)))
m = len(sorted_B)

# Sort cakes by A descending then B descending
cakes.sort(key=lambda x: (-x[0], -x[1]))

# Group by A
groups = []
current_A = None
current_group = []
for cake in cakes:
    A = cake[0]
    if A != current_A:
        if current_group:
            groups.append(current_group)
        current_group = [cake]
        current_A = A
    else:
        current_group.append(cake)
groups.append(current_group)

# Initialize segment tree
st = SegmentTreeMax(m)

max_answer = 0

for group in groups:
    dps = []
    for cake in group:
        A_j, B_j, C_j = cake
        # Compute q_idx = bisect_right(B_j)
        q_idx = bisect.bisect_right(sorted_B, B_j)
        # Query from q_idx to m
        max_prev = st.query(q_idx, m)
        current_dp = C_j + (max_prev if max_prev > 0 else 0)
        dps.append(current_dp)
        if current_dp > max_answer:
            max_answer = current_dp
    # Update the segment tree for each cake in the group
    for cake, current_dp in zip(group, dps):
        B_j = cake[1]
        # Find the compressed index
        b_idx = bisect.bisect_left(sorted_B, B_j)
        # Update the segment tree at b_idx with current_dp
        st.update(b_idx, current_dp)

print(max_answer)
0