結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0_sample1.txt AC 91 ms
53,720 KB
0_sample2.txt AC 90 ms
53,720 KB
0_sample3.txt AC 91 ms
53,720 KB
0_sample4.txt AC 102 ms
53,716 KB
1_1.txt AC 99 ms
53,704 KB
1_2.txt AC 105 ms
53,716 KB
1_3.txt AC 92 ms
53,716 KB
1_4.txt AC 89 ms
53,720 KB
1_5.txt AC 90 ms
53,724 KB
2_1.txt AC 89 ms
53,708 KB
2_2.txt AC 90 ms
53,720 KB
2_3.txt AC 90 ms
53,724 KB
2_4.txt AC 91 ms
53,720 KB
2_5.txt AC 91 ms
53,716 KB
2_6.txt AC 90 ms
53,716 KB
2_7.txt AC 89 ms
53,712 KB
2_8.txt AC 91 ms
53,716 KB
2_9.txt AC 95 ms
53,720 KB
2_10.txt AC 102 ms
53,716 KB
2_11.txt AC 111 ms
53,716 KB
2_12.txt AC 91 ms
53,724 KB
3_1.txt AC 192 ms
58,532 KB
3_2.txt AC 171 ms
58,352 KB
3_3.txt AC 155 ms
57,712 KB
3_4.txt AC 158 ms
57,716 KB
4_1.txt AC 173 ms
57,924 KB
4_2.txt AC 171 ms
58,068 KB
4_3.txt AC 161 ms
58,124 KB
5_1.txt AC 1,988 ms
125,848 KB
5_2.txt AC 1,878 ms
125,892 KB
6_1.txt AC 1,931 ms
122,656 KB
6_2.txt AC 1,985 ms
122,600 KB
6_3.txt AC 872 ms
119,648 KB
6_4.txt AC 630 ms
99,672 KB
6_5.txt AC 912 ms
121,152 KB
6_6.txt AC 1,888 ms
125,284 KB
6_7.txt AC 867 ms
119,704 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