結果

問題 No.1826 Fruits Collecting
ユーザー lam6er
提出日時 2025-03-26 15:55:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 951 ms / 2,000 ms
コード長 2,083 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 155,736 KB
最終ジャッジ日時 2025-03-26 15:56:39
合計ジャッジ時間 21,583 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    
    fruits = []
    for _ in range(N):
        T = int(data[idx])
        X = int(data[idx+1])
        V = int(data[idx+2])
        idx += 3
        if T >= abs(X):
            a = T + X
            b = T - X
            fruits.append((a, b, V))
    
    if not fruits:
        print(0)
        return
    
    # Sort by 'a', then by 'b'
    fruits.sort(key=lambda x: (x[0], x[1]))
    
    # Compress 'b' values
    b_values = [b for (a, b, v) in fruits]
    b_sorted = sorted(list(set(b_values)))
    max_b = len(b_sorted)
    
    # Fenwick Tree for maximum
    class FenwickTreeMax:
        def __init__(self, size):
            self.n = size
            self.tree = [-float('inf')] * (self.n + 2)  # 1-based
        
        def update(self, idx, value):
            while idx <= self.n:
                if value > self.tree[idx]:
                    self.tree[idx] = value
                else:
                    break  # No need to proceed further
                idx += idx & -idx
        
        def query(self, idx):
            res = -float('inf')
            while idx > 0:
                if self.tree[idx] > res:
                    res = self.tree[idx]
                idx -= idx & -idx
            return res
    
    # Compress the b values to indices starting from 1
    ft = FenwickTreeMax(len(b_sorted))
    max_value = 0
    for a, b, v in fruits:
        pos = bisect.bisect_left(b_sorted, b) + 1  # 1-based index
        current_max = ft.query(pos)
        if current_max == -float('inf'):
            current_max = 0
        current_dp = current_max + v
        if current_dp > max_value:
            max_value = current_dp
        # Update the Fenwick tree if this is better than the existing value at pos
        existing = ft.query(pos)  # Current max up to pos
        if current_dp > existing:
            ft.update(pos, current_dp)
    
    print(max_value)

if __name__ == '__main__':
    main()
0