Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]

for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1

    if l or r:
        lr.append([l,r])


idleR=10**8
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    #print(dp[n][X],n,xl,xr)
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
    #    print(stack)
dp=[defaultdict(int) for i in range(len(lr))]
stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()

    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            #print("a")
            #print(n+1,L,r+R-l)
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        #print(l,r)
        if l==r==0:
            print("Yes")
            exit()


print("No")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)


if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]

stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]


        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)





    else:
        if l<=rlst:
            R=rlst-l
        else:
            continue
        if r<=llst:
            L=llst-r
        else:
            continue
        if L==R:
            print("Yes")
            exit()



print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0): l |= 2
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
  if h[0] >= 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1
for i in range(c, N): hpush(h, t[i][0] - t[i][1])
while len(h): l += -h.pop()
if l == 0: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0): l |= 2
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
  if h[0] >= 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1


print("Yes")

Submission status: Wrong Answer

Solution code:
import sys

input = raw_input
input = lambda : sys.stdin.readline().replace("\n", "")

n = int(input())
 
def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r
 
 
ind = 0
pairs = []
ls = []
rs = []
 
n_cond = 2
sum_ls = [0, 0]
sum_rs = [0, 0]
nokori_l = 0
nokori_r = 0
for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        for cond_i in range(n_cond):
            sum_l = sum_ls[cond_i]
            sum_r = sum_rs[cond_i]

            sum_l1 = sum_l
            sum_r1 = r
            mid1 = sum_r + l
            if mid1 < 0:
                sum_l1 += mid1
            else:
                sum_r1 += mid1
     
            sum_l2 = l
            sum_r2 = sum_r
            mid2 = r + sum_l
            if mid2 < 0:
                sum_l2 += mid2
            else:
                sum_r2 += mid2
     
            if cond_i == 0:
                if sum_r2 <= sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1
            else:
                if sum_r2 < sum_r1:
                    sum_l = sum_l2
                    sum_r = sum_r2
                else:
                    sum_l = sum_l1
                    sum_r = sum_r1

            sum_ls[cond_i] = sum_l
            sum_rs[cond_i] = sum_r

    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r
 
flag = False
for cond_i in range(n_cond):
    sum_l = sum_ls[cond_i]
    sum_r = sum_rs[cond_i]

    right_side = sum_r + nokori_l
    left_side = nokori_r + sum_l
     
    if left_side >= 0 and right_side <= 0:
        if left_side + right_side == 0:
            #print("Yes")
            flag = True
        else:
            #print("No")
            pass
    else:
        #print("No")
        pass

if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
key = [0]*n
flag1, flag2 = False, False
sum1, sum2 = 0, 0
for i in range(n):
  s = input()
  k1 = 0
  while s[k1] == ")":
    k1 += 1
    if k1 == len(s):
      break
  k2 = len(s)-k1
  for j in range(k1, len(s)):
    if s[j] == ")":
      k2 -= 2
  if not k1:
    flag1 = True
  if not k1:
    flag2 = True
  sum1 += k1
  sum2 += k2
  key[i] = (k1, k2-k1, k2)

key.sort()
if flag1 and flag2 and sum1 == sum2:
  sub = 0
  flag = True
  for i in range(n):
    if sub < key[i][0]:
      flag = False
      break
    sub -= key[i][0]
    sub += key[i][2]
  if flag:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
dicpos = {}
dicneg = {}

N = int(input())
for i in range(N):
  buf = [0]
  for s in input():
    if s=="(":
      buf.append(buf[-1] + 1)
    else:
      buf.append(buf[-1] - 1)
  low = min(buf)
  last = buf[-1]
  if last>0:
    if low in dicpos:
      dicpos[low].append(last)
    else:
      dicpos[low] = [last]
  else:
    if low in dicneg:
      dicneg[low].append(last)
    else:
      dicneg[low] = [last]
neg_sorted = sorted(dicneg.items(), key=lambda x:x[0])
pos_sorted = sorted(dicpos.items(), key=lambda x:x[0], reverse=True)
#print(neg_sorted)
#print(pos_sorted)
summ = 0
flag = 0
for i in pos_sorted:
  for j in i[1]:
    if flag == 1:
      break
    if summ + i[0] < 0:
      flag = 1
      print("No")
      break
    summ += j
if flag == 0:
  for i in neg_sorted:
    if flag == 1:
      break
    for j in sorted(i[1], reverse=True):
      if summ + i[0] < 0:
      	flag = 1
      	print("No")
      	break 
      summ += j
if flag == 0:
  if summ == 0:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:









def     process(tab, first, end):
    total = first
    #print(tab)
    for i in tab:
        total += i[0]
        if (total < 0):
            return ("No")
    return ("Yes")




N  = int(input())

first = -1
last = -1
tab = []
for i in range(N):
    s = input()
    total = 0
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and first == -1):
        first = apres
    elif (apres == 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    total += avant - apres
#print(tab)
#print(total)
tab = sorted(tab)[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(sorted(tab), first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Wrong Answer

Solution code:
dicpos = {}
dicneg = {}

N = int(input())
for i in range(N):
  buf = [0]
  for s in input():
    if s=="(":
      buf.append(buf[-1] + 1)
    else:
      buf.append(buf[-1] - 1)
  low = min(buf)
  last = buf[-1]
  if last>0:
    if low in dicpos:
      dicpos[low].append(last)
    else:
      dicpos[low] = [last]
  else:
    if low in dicneg:
      dicneg[low].append(last)
    else:
      dicneg[low] = [last]
neg_sorted = sorted(dicneg.items(), key=lambda x:x[0])
pos_sorted = sorted(dicpos.items(), key=lambda x:x[0], reverse=True)
#print(neg_sorted)
#print(pos_sorted)
summ = 0
flag = 0
for i in pos_sorted:
  for j in i[1]:
    if summ + i[0] < 0:
      flag = 1
      print("No")
      break
    summ += j
if flag == 0:
  for i in neg_sorted:
    for j in sorted(i[1], reverse=True):
      if summ + i[0] < 0:
      	flag = 1
      	print("No")
      	break 
      summ += j
if flag == 0:
  if summ == 0:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
dicpos = {}
dicneg = {}

N = int(input())
for i in range(N):
  buf = [0]
  for s in input():
    if s=="(":
      buf.append(buf[-1] + 1)
    else:
      buf.append(buf[-1] - 1)
  low = min(buf)
  last = buf[-1]
  if last>0:
    if low in dicpos:
      dicpos[low].append(last)
    else:
      dicpos[low] = [last]
  else:
    if low in dicneg:
      dicneg[low].append(last)
    else:
      dicneg[low] = [last]
neg_sorted = sorted(dicneg.items(), key=lambda x:x[0])
pos_sorted = sorted(dicpos.items(), key=lambda x:x[0], reverse=True)
print(neg_sorted)
print(pos_sorted)
summ = 0
flag = 0
for i in pos_sorted:
  for j in i[1]:
    if summ + i[0] < 0:
      flag = 1
      print("No")
      break
    summ += j
if flag == 0:
  for i in neg_sorted:
    for j in sorted(i[1], reverse=True):
      if summ + i[0] < 0:
      	flag = 1
      	print("No")
      	break 
      summ += j
if flag == 0:
  if summ == 0:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
r = []
for _i in range(n):
    s = input()
    p = 0
    m = [0]
    for j in range(len(s)):
        if s[j]=='(':
            p += 1
        else:
            p -= 1
        m.append(p)
    r.append([min(m), p])
r.sort()
result = 0
for x, y in r[::-1]:
    if result+x<0:
        result = -1
        break
    result += y

if result==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=list(map(list,zip(s,t)))

for i in range(n):
    now,mi=0,0
    for j in st[i][0]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[2]>=0,st)),list(filter(lambda x:x[2]<0 and x[1]>=0,st)),list(filter(lambda x:x[2]<0 and x[1]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
v.sort(reverse=True,key=lambda z:z[2])
w.sort(reverse=True,key=lambda z:z[1])
w.sort(reverse=True,key=lambda z:z[2])
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][1]
    elif i<lu+lv:
        if now2+v[i-lu][2]<0:
            print("No")
            break
        now2+=v[i-lu][1]
    else:
        if now2+w[i-lu-lv][2]<0:
            print("No")
            break
        now2+=w[i-lu-lv][1]
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
r = []
for _i in range(n):
    s = input()
    p = 0
    m = []
    for j in range(len(s)):
        if s[j]=='(':
            p += 1
        else:
            p -= 1
        m.append(p)
    r.append([min(m), p])
r.sort()
result = 0
for x, y in r[::-1]:
    if result+x<0:
        result = -1
        break
    result += y

if result==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l |= 1
  if rs[i] == 0 and (ls[i] > 0): l |= 2
if l < 3:
  print("No")
  exit(0)
l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0: break
  if h[0] >= 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1

print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
r = []
for _i in range(n):
    s = input()
    p = 0
    m = []
    for j in range(len(s)):
        if s[j]=='(':
            p += 1
        else:
            p -= 1
        m.append(p)
    r.append([min(m), p])
r.sort(reverse=True)
result = 0
for x, y in r:
    if result+x<0:
        result = -1
        break
    result += y

if result==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    sm = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        if p >= 0:
            s.append((m,p))
        else:
            sm.append((m,p))
    s.sort(reverse = True)
    q = []
    k = 0
    i = 0
    while q or (i < len(s)):
        while i < len(s) and s[i][0]+k >= 0:
            heappush(q,-s[i][1])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
        if k < 0:
            print("No")
            return
    sm.sort(key = lambda x:(x[0],-x[1]))
    if q or i < len(s):
        print("No")
        return
    for m,p in sm:
        if m+k < 0:
            print("No")
        k += p
    if k != 0:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = []
for i in range(n):
    cnt = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt += 1
        else:
            cnt -= 1
    x.append([cnt, len(s[i]), s[i]])
x.sort(key = lambda x:(x[0],-x[1]), reverse=True)
x = deque(x)
tmp = deque()
stack = []
flag = False
while x:
    _, _, v = x.popleft()
    if not flag:
        if v[0] == '(':
            flag = True
            for i in v:
                if i == '(':
                    stack.append(i)
                else:
                    if stack:
                        stack.pop()
                    else:
                        print('No')
                        quit()
            while tmp:
                u = tmp.popleft()
                for i in u:
                    if i == '(':
                        stack.append(i)
                    else:
                        if stack:
                            stack.pop()
                        else:
                            print('No')
                            quit()
        else:
            tmp.append(v)
    else:
        for i in v:
            if i == '(':
                stack.append(i)
            else:
                if stack:
                    stack.pop()
                else:
                    print('No')
                    quit()
if stack:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
ans=0

mo=998244353

n=I()
b=[]
L,R=0,0
for i in range(n):
    s=S_()
    ns=len(s)
    a=[0]
    m,M=0,0
    l,r=0,0
    lv=0
    for j in s:
        if j=='(':
            lv+=1
            l+=1
            x=a[-1]+1
            a+=[a[-1]+1]
            if M<x:
                M=x
        else:
            lv-=1
            r+=1
            x=a[-1]-1
            a+=[a[-1]-1]
            if m>x:
                m=x
    y=( (M)*10**14+(lv+m)*10**7+min(m,0)*10**21+m,lv,l,r,m,M)
    #b+=[(l,r,m,M,s)]
    b+=[y]
    L+=l
    R+=r

fl=True

if L!=R:
    fl=False
    
b.sort(key=lambda x:-x[0])

x=0

for i in b:
    sc,lv,l,r,m,M=i
    
    if x+m<0:
        fl=False
        #show('False',i,(x,m))
        
    x+=lv

    #show('x=',x,lv,(l,r),(m,M),sc)

if x==0:
    fl=fl and True
    

print(Yn[not fl])

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)


if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**8
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]
main(-1,0,0)
#stack=[[0,L,R]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        R=rlst-l
        L=llst-r
        if L==R and L>=0 and R>=0:
            print("No")
            exit()



print("No")