結果

問題 No.1826 Fruits Collecting
ユーザー lam6er
提出日時 2025-04-09 20:58:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,262 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 174,304 KB
最終ジャッジ日時 2025-04-09 21:00:18
合計ジャッジ時間 19,545 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    
    fruits = []
    initial_added = False
    for _ in range(N):
        T = int(input[idx])
        X = int(input[idx+1])
        V = int(input[idx+2])
        idx +=3
        a = T - X
        b = T + X
        if a >=0 and b >=0:
            # check if T >= abs(X)
            if T >= abs(X):
                fruits.append((a, b, V, False))
    
    # Add the initial point (0,0,0)
    fruits.append((0, 0, 0, True))  # is_initial=True
    
    # Sort the fruits:
    # - by a ascending
    # - among same a: initial comes first, then higher b, then higher V
    fruits.sort(key=lambda x: (x[0], 0 if x[3] else 1, -x[1], -x[2]))
    
    # Extract all b for coordinate compression
    b_list = [f[1] for f in fruits]
    # Sort and dedup
    sorted_b = sorted(set(b_list))
    # Assign rank starting from 1
    rank = {b: i+1 for i, b in enumerate(sorted_b)}  # 1-based indexing
    
    max_rank = len(sorted_b)
    
    # Fenwick Tree for max query
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(size+1)  # 1-based
        
        def update(self, idx, value):
            while idx <= self.size:
                if self.tree[idx] < value:
                    self.tree[idx] = value
                else:
                    break  # no need to proceed further
                idx += idx & -idx
        
        def query(self, idx):
            res = 0
            while idx >0:
                if self.tree[idx] > res:
                    res = self.tree[idx]
                idx -= idx & -idx
            return res
    
    ft = FenwickTree(max_rank)
    max_dp = 0
    
    for f in fruits:
        a, b, v, is_initial = f
        current_rank = rank[b]
        
        # Query max_dp up to current_rank
        current_max = ft.query(current_rank)
        current_dp = current_max + v
        if current_dp > max_dp:
            max_dp = current_dp
        
        # Update Fenwick tree
        if current_dp > ft.query(current_rank):
            ft.update(current_rank, current_dp)
    
    print(max_dp)
    
if __name__ == "__main__":
    main()
0