結果

問題 No.777 再帰的ケーキ
ユーザー torikumino
提出日時 2019-01-11 23:46:04
言語 PyPy3
(6.0.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 656 Byte
コンパイル時間 254 ms
使用メモリ 130,132 KB
最終ジャッジ日時 2019-04-28 03:43:44

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample1.txt AC 108 ms
66,064 KB
0_sample2.txt AC 109 ms
66,072 KB
0_sample3.txt AC 109 ms
66,068 KB
0_sample4.txt AC 109 ms
66,064 KB
1_1.txt AC 108 ms
66,052 KB
1_2.txt AC 109 ms
66,072 KB
1_3.txt AC 110 ms
66,064 KB
1_4.txt AC 111 ms
66,056 KB
1_5.txt AC 107 ms
66,064 KB
2_1.txt AC 110 ms
66,060 KB
2_2.txt AC 108 ms
66,060 KB
2_3.txt AC 107 ms
66,064 KB
2_4.txt AC 111 ms
66,068 KB
2_5.txt AC 107 ms
66,064 KB
2_6.txt AC 110 ms
66,060 KB
2_7.txt AC 109 ms
66,048 KB
2_8.txt AC 109 ms
66,056 KB
2_9.txt AC 109 ms
66,064 KB
2_10.txt AC 109 ms
66,060 KB
2_11.txt AC 110 ms
66,060 KB
2_12.txt AC 110 ms
66,064 KB
3_1.txt AC 194 ms
68,936 KB
3_2.txt AC 185 ms
68,912 KB
3_3.txt AC 173 ms
68,756 KB
3_4.txt AC 171 ms
68,756 KB
4_1.txt AC 187 ms
68,660 KB
4_2.txt AC 188 ms
68,656 KB
4_3.txt AC 176 ms
68,820 KB
5_1.txt TLE -
5_2.txt TLE -
6_1.txt TLE -
6_2.txt TLE -
6_3.txt AC 1,065 ms
128,812 KB
6_4.txt AC 758 ms
107,892 KB
6_5.txt AC 1,169 ms
130,132 KB
6_6.txt TLE -
6_7.txt AC 1,073 ms
128,820 KB
テストケース一括ダウンロード

ソースコード

diff #
from bisect import *
N = int(input())
A = sorted((tuple(map(int, input().split())) for _ in range(N)),
        key=lambda x: (x[0],-x[1]))
P = [0]*N
G = [0]*N
t = sorted(range(N), key=lambda x: A[x][1])
x = -1
for i in range(N)[::-1]:
    j = t[i]
    P[j] = i
    if x>=0 and A[j][1]==A[x][1]:
        G[j] = G[x]
    else:
        G[j] = i+1
        x = j
B = [0]*(N+2)
def U(i, v):
    while i <= N:
        B[i] = max(B[i], v)
        i += i&-i
def Q(i):
    v = 0
    while i > 0:
        v = max(v, B[i])
        i -= i&-i
    return v
for i in range(N)[::-1]:
    _, b, c = A[i]
    j = N-G[i]
    v = Q(j)
    j = N-P[i]
    U(j, v+c)
print(max(B))
0