結果

問題 No.3061 Cut and Maximums
ユーザー 👑 rin204
提出日時 2024-07-07 18:51:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 262 ms / 2,000 ms
コード長 1,152 bytes
コンパイル時間 144 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 156,252 KB
最終ジャッジ日時 2024-07-07 18:51:22
合計ジャッジ時間 7,851 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

def CartesianTree(A):
    n = len(A)
    P = [-1] * n
    B = [-1] * n
    p = -1

    for i, a in enumerate(A):
        while p >= 0 and a < A[B[p]]:
            j = B[p]
            p -= 1
            if p >= 0 and a < A[B[p]]:
                P[j] = B[p]
            else:
                P[j] = i

        p += 1
        B[p] = i

    for i in range(p, 0, -1):
        P[B[i]] = B[i - 1]

    i = B[0]
    P[i] = i
    return P


n = int(input())
P = list(map(int, input().split()))
for i in range(n):
    P[i] -= 1

S = input()

if S[-1] == "W":
    if "B" in S:
        print(-1)
    else:
        print(0)
    exit()

idx = P.index(n - 1)
P = P[idx:] + P[:idx]

ct = CartesianTree([-p for p in P])
child = [[] for _ in range(n)]
for i, p in enumerate(ct):
    if p != i:
        child[p].append(i)

route = []
st = [0]
while st:
    u = st.pop()
    route.append(u)
    for v in child[u]:
        st.append(v)

dp = [0] * n
for u in route[::-1]:
    for v in child[u]:
        if S[P[u]] == "B":
            dp[u] = max(dp[u], dp[v])
        else:
            dp[u] += dp[v]
    if S[P[u]] == "B" and dp[u] == 0:
        dp[u] = 1

print(dp[0])
0