結果

問題 No.3148 Min-Cost Destruction of Parentheses
コンテスト
ユーザー sasa8uyauya
提出日時 2025-05-17 07:41:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 982 ms / 4,000 ms
コード長 967 bytes
コンパイル時間 489 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 122,968 KB
最終ジャッジ日時 2025-05-17 07:41:24
合計ジャッジ時間 16,600 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
s="("+input()+")"
a=[0]+list(map(int,input().split()))
p=[0]*(n+1)
g=0
q=[]
for c in s:
  if c=="(":
    if len(q)>0:
      p[g]=q[-1]
    q+=[g]
    g+=1
  else:
    q.pop()

def root(x):
  p=x
  l=[p]
  while r[p]!=p:
    p=r[p]
    l+=[p]
  for p in l:
    r[p]=l[-1]
  return r[x]

def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  if rx>ry:
    rx,ry=ry,rx
  r[ry]=rx
  return

A=sum(a)
from heapq import heappush,heappop
r=list(range(n+1))
v=[]
rc0=0
rc1=1
v+=[(-(rc0/(rc0+rc1)),0,rc0,rc1,0)]
q=[]
for i in range(1,n+1):
  c0=a[i]
  c1=1
  heappush(q,(-(c0/(c0+c1)),i,c0,c1,0))
  v+=[(-(c0/(c0+c1)),i,c0,c1,0)]
while len(q)>0:
  a,i,c0,c1,f=heappop(q)
  if root(i)!=i:
    continue
  if (a,i,c0,c1,f)!=v[i]:
    continue
  _,pi,pc0,pc1,pf=v[root(p[i])]
  ni=pi
  nc0=pc0+c0
  nc1=pc1+c1
  nf=pf+f+pc1*c0
  na=-(nc0/(nc0+nc1))
  v[pi]=(na,ni,nc0,nc1,nf)
  union(i,pi)
  if pi>0:
    heappush(q,(na,ni,nc0,nc1,nf))
print(v[0][-1])
0