結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample1.txt AC 126 ms
53,716 KB
0_sample2.txt AC 130 ms
53,720 KB
0_sample3.txt AC 129 ms
53,720 KB
0_sample4.txt AC 124 ms
53,716 KB
1_1.txt AC 132 ms
53,708 KB
1_2.txt AC 129 ms
53,724 KB
1_3.txt AC 123 ms
53,720 KB
1_4.txt AC 132 ms
53,720 KB
1_5.txt AC 127 ms
53,712 KB
2_1.txt AC 124 ms
53,708 KB
2_2.txt AC 129 ms
53,716 KB
2_3.txt AC 123 ms
53,716 KB
2_4.txt AC 128 ms
53,724 KB
2_5.txt AC 131 ms
53,724 KB
2_6.txt AC 127 ms
53,720 KB
2_7.txt AC 128 ms
53,708 KB
2_8.txt AC 122 ms
53,712 KB
2_9.txt AC 127 ms
53,720 KB
2_10.txt AC 129 ms
53,712 KB
2_11.txt AC 127 ms
53,720 KB
2_12.txt AC 125 ms
53,724 KB
3_1.txt AC 220 ms
58,528 KB
3_2.txt AC 221 ms
58,336 KB
3_3.txt AC 192 ms
57,716 KB
3_4.txt AC 196 ms
57,712 KB
4_1.txt AC 214 ms
57,928 KB
4_2.txt AC 208 ms
58,060 KB
4_3.txt AC 202 ms
58,116 KB
5_1.txt TLE -
5_2.txt TLE -
6_1.txt TLE -
6_2.txt TLE -
6_3.txt AC 1,168 ms
119,644 KB
6_4.txt AC 799 ms
99,564 KB
6_5.txt AC 1,086 ms
121,148 KB
6_6.txt TLE -
6_7.txt AC 1,222 ms
119,684 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