結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2021-02-11 09:34:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,237 ms / 2,000 ms |
コード長 | 1,480 bytes |
コンパイル時間 | 287 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 179,200 KB |
最終ジャッジ日時 | 2024-07-17 22:58:17 |
合計ジャッジ時間 | 11,569 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
import syssys.setrecursionlimit(10**6)int1 = lambda x: int(x)-1p2D = lambda x: print(*x, sep="\n")def II(): return int(sys.stdin.buffer.readline())def MI(): return map(int, sys.stdin.buffer.readline().split())def MI1(): return map(int1, sys.stdin.buffer.readline().split())def LI(): return list(map(int, sys.stdin.buffer.readline().split()))def LI1(): return list(map(int1, sys.stdin.buffer.readline().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def BI(): return sys.stdin.buffer.readline().rstrip()def SI(): return sys.stdin.buffer.readline().rstrip().decode()# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]dij = [[(-1, 0), (1, 0)], [(0, -1), (0, 1)]]inf = 10**16# md = 998244353# md = 10**9+7class BitMax:def __init__(self, n):self.inf = 10**9self.n = n+3self.table = [-self.inf]*(self.n+1)def update(self, i, x):i += 1while i <= self.n:if x > self.table[i]: self.table[i] = xi += i & -idef max(self, i):i += 1res = -self.infwhile i > 0:if self.table[i] > res: res = self.table[i]i -= i & -ireturn resmx = 200005n = II()abc = LLI(n)abc.sort(key=lambda x: (x[0], -x[1]))enc = {x: i+1 for i, x in enumerate(sorted(set(b for a, b, c in abc)))}bit = BitMax(mx)bit.update(0, 0)for a, b, c in abc:b = enc[b]cur = bit.max(b-1)+cbit.update(b, cur)print(bit.max(mx-1))