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

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
n = int(input())
s = [input() for _ in range(n)]
t = []
p = []
for i in range(n):
    k = 0
    m = 0
    for c in s[i]:
        if c == '(':
            k += 1
        elif c == ')':
            k -= 1
            m = min(k, m)
    if k >= 0:
        t.append((-m, k))
    else:
        k = 0
        m = 0
        for c in s[i][::-1]:
            if c == ')':
                k += 1
            elif c == '(':
                k -= 1
                m = min(k, m)
        p.append((-m, k))
t.sort()
p.sort()
hq = []
hq1 = []
d = 0
idx = 0
for i in range(len(t)):
    while idx < len(t) and d >= t[idx][0]:
        m, k = t[idx]
        heapq.heappush(hq, (-k, m))
        idx += 1
    if hq:
        k, m = heapq.heappop(hq)
    else:
        print('No')
        break
    d -= k
else:
    d1 = 0
    idx = 0
    for i in range(len(p)):
        while idx < len(p) and d1 >= p[idx][0]:
            m, k = p[idx]
            heapq.heappush(hq1, (-k, m))
            idx += 1
            if hq1:
                k, m = heapq.heappop(hq1)
            else:
                print('No')
                break
            d1 -= k
    else:
        if d == d1:
            print('Yes')
        else:
            print('No')

Solution (Python):
N = int(input())
S = [input() for _ in range(N)]

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  s = S[i]
  ma = 0
  l = 0
  r = 0
  for j in s:
    if j == ")":
      r += 1
    else:
      l += 1
    ma = max(ma, r - l)
  D[i] = [l - r, ma, s]

cnt = 0
P = []
M = []
for x, y ,s in D:
  if x >= 0:
    if y <= 0:
      cnt += x
    else:
      P.append([x, y])
  else:
    M.append([x, y, s])

P.sort(key = lambda x:x[1])

for x, y in P:
  if y > cnt:
    print("No")
    exit()
  cnt += x

if len(M) == 0:
  if cnt == 0:
    print("Yes")
  else:
    print("No")
  exit()

M.sort(reverse = True)
M.sort(key = lambda x:x[1], reverse = True)

for i in range(len(M)):
  x, y, s = M[i]
  if x == -y:
    g = x
    M[i] = [0, 0, ""]
    break
else:
  print("No")
  exit()

for x, y, s in M:
  if cnt < y:
    print("No")
    exit()
  cnt += x

if cnt + g == 0:
  print("Yes")
else:
  print("No")

Solution (Python):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
pos = []
zero = []
neg = []
for _ in range(N):
    S = input().rstrip()
    m = s = 0
    for c in S:
        if c == '(':
            s += 1
        else:
            s -= 1
            m = min(m, s)
    if s > 0:
        heappush(pos, (-m, s)) 
    elif s == 0:
        heappush(zero, (m, s))
    else:
        heappush(neg, (m - s, s)) 
num = 0
while pos:
    m, s = heappop(pos)
    if num - m < 0:
        print('No')
        exit()
    num += s
while zero:
    m, s = heappop(zero)
    if num + m < 0:
        print('No')
        exit()
while neg:
    m, s = heappop(neg)
    m += s
    if num + m < 0:
        print('No')
        exit()
    num += s
if num == 0:
    print('Yes')
else:
    print('No')

Solution (Python):


def simplify(s):
    res = []
    o = 0
    e = 0
    for c in s:
        if c == ")" and res and res[-1] == "(":
            res.pop()
            o -= 1
        else:
            res.append(c)
            if c == "(":
                o += 1
            else:
                e += 1
    return res, o, e


def submit():
    n = int(input())
    slist = []
    for _ in range(n):
        slist.append(simplify(input()))

    open_only = []
    end_only = []
    mix = []
    for s, o, e in slist:
        if o > 0 and e == 0:
            open_only.append((s, o, e))
        elif o == 0 and e > 0:
            end_only.append((s, o, e))
        else:
            mix.append((s, o, e))
    mix.sort(key=lambda x: x[1] - x[2], reverse=True)

    check = 0
    for s, o, e in open_only:
        check += o

    for s, o, e in mix:
        check -= e
        if check < 0:
            print("No")
            return
        check += o

    for s, o, e in end_only:
        check -= e
    
    if check == 0:
        print("Yes")
    else:
        print("No")


submit()

Solution (Python):
def main():
    N = int(input())

    tmp = 0
    lst1 = [] 
    lst1_append = lst1.append

    lst2 = [] 
    lst2_append = lst2.append

    minas = 0

    for _ in range(N):
        S = list(input())
        min_ = 0
        total = 0
        for s in S:
            if s == '(':
                total += 1
            else:
                total -= 1
                min_ = min(min_, total)
        if min_ == 0:
            tmp += total
        else:
            if total > 0:
                lst1_append([min_, total])
            elif total == min_:
                minas += total
            else:
                lst2_append([min_, total])

    lst1.sort(key = lambda x: x[0], reverse = True) 
    for a, b in lst1:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b

    lst2.sort(key = lambda x: x[1], reverse = True)
    lst2.sort(key = lambda x: x[0], reverse = False) 

    
    for a, b in lst2:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b
    
    tmp += minas

    if tmp == 0:
        print ('Yes')
    else:
        print ('No')

if __name__ == '__main__':
    main()

Solution (Python):
def solve():
  n = int(input())
  s = [input() for _ in range(n)]
  l = []
  for si in s:
      lparen = rparen = 0
      for c in si:
          if c == '(':
              lparen += 1
          else:
              if lparen > 0:
                  lparen -= 1
              else:
                  rparen += 1
      l.append((rparen, lparen))
  inc = []
  dec = []
  for p, q in l:
      if p < q:
          inc.append((p, q))
      else:
          dec.append((p, q))
  inc.sort()
  k = 0
  for p, q in inc:
      if k < p:
          print('No')
          return
      k = k - p + q
  dec.sort(key=lambda x: x[1])
  t = 0
  for p, q in dec:
      if t < q:
          print('No')
          return
      t = t - q + p
  if k == t:
      print('Yes')
  else:
      print('No')
  return


solve()

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    Sss = [input().rstrip() for _ in range(N)]

    numL = numR = 0
    Pluss, Evens, Minuss = [], [], []
    for Ss in Sss:
        nums = [0] + [1 if S == '(' else -1 for S in Ss]
        nums = list(accumulate(nums))
        x = min(nums)
        y = nums[-1] - x
        x, y = abs(x), abs(y)
        if x == 0:
            numL += y
        elif y == 0:
            numR += x
        else:
            if x > y:
                Minuss.append((x, y))
            elif x < y:
                Pluss.append((x, y))
            else:
                Evens.append((x, y))

    Pluss.sort(key=lambda x: x[0])
    Minuss.sort(key=lambda x: x[1], reverse=True)

    v = numL
    for x, y in Pluss:
        v -= x
        if v < 0:
            return False
        v += y
    for x, y in Evens:
        v -= x
        if v < 0:
            return False
        v += y
    for x, y in Minuss:
        v -= x
        if v < 0:
            return False
        v += y
    v -= numR
    return v == 0


if solve():
    print('Yes')
else:
    print('No')

Solution (Python):
n = int(input())
left = []
mid = []
midminus = []
right = []
L = []
R = []

for i in range(n):
    s = input()
    l = 0
    r = 0
    for x in s:
        if x == '(':
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    if l > 0 and r == 0:
        left.append((l, r))
    elif l > 0 and r > 0:
        if l > r:
            mid.append((r, l))  
        else:
            midminus.append((r,l))
    elif l == 0 and r > 0:
        right.append((l, r))
    L.append(l)
    R.append(r)

if sum(L) != sum(R):
    print('No')
    exit()

A = 0
B = 0
for x in left:
    A += x[0]
for x in right:
    B += x[1]

mid = sorted(mid, key=lambda x: (x[0],-x[1]))
midminus = sorted(midminus,key= lambda x:x[0]-x[1])
mid += midminus

l = A
r = 0
for a, b in mid:
    if l < a:
        print('No')
        exit()
    l -= a
    l += b

print('Yes')

Solution (Python):
def main():

    import sys, math
    
    
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    
    INF = int(1e9)
    mod = int(1e9)+7

    n=int(data())
    l1=[]
    l2=[]
    cnt1=0
    cnt2=0
    for i in range(n):
        s=data()
        o=c=0
        for j in s:
            if j=='(':
                o+=1
            else:
                if o>0:
                    o-=1
                else:
                    c+=1
        if o==0:
            if c!=0:
                cnt2+=c
        elif c==0:
            cnt1+=o
        else:
            if c>o:
                l2.append([c,o])
            else:
                l1.append([c,o])
    l1.sort(key=lambda x:x[0])
    flag=True
    for i in l1:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    l2.sort(key=lambda x: x[1],reverse=True)
    l2.sort(key=lambda x: x[0],reverse=True)
    for i in l2:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    if flag==True:
        if cnt1-cnt2==0:
            print("Yes")
        else:
            print("No")
    else:
        print("No")

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok(a):
    s = 0
    for i, j, _, _ in a:
        if s + j < 0:
            print("No")
            exit()
        s += i

ok(a)
ok(b)
print("Yes")

Solution (Python):
N = int(input())
left = []
right = []
last = None
for i in range(N):
	s = input()
	l = len(s)
	r_needed = 0
	l_needed = 0
	for j in range(l):
		if s[j] == "(":
			r_needed += 1
		elif s[j] == ")" and r_needed > 0:
			r_needed -= 1

		if s[l-1 - j] == ")":
			l_needed += 1
		elif s[l-1 - j] == "(" and l_needed > 0:
			l_needed -= 1
	if r_needed < l_needed:
		right.append((-r_needed, l_needed))
	else:
		left.append((l_needed, -r_needed))

left.sort()
right.sort()
rest_l = 0
for l in left:
	l_needed = l[0]
	r_needed = -l[1]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l += r_needed - l_needed
for r in right:
	l_needed = r[1]
	r_needed = -r[0]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l -= l_needed
	rest_l += r_needed
if rest_l != 0:
	print("No")
else:
	print("Yes")

Solution (Python):
n = int(input())
s = [input() for _ in range(n)]

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in mr:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()

Solution (Python):
import sys
import heapq
input = sys.stdin.readline

N = int(input())

forward = []
backward = []

for _ in range(N):
    pos = 0
    Min = 0
    for c in input()[:-1]:
        if c == '(':
            pos += 1
        else:
            pos -= 1
            Min = min(Min, pos)
    if pos >= 0:
        heapq.heappush(forward, (-Min, pos))
    else:
        heapq.heappush(backward, (pos-Min, -pos))

ansflg = True
pos1 = 0
while forward:
    down, pos = heapq.heappop(forward)
    if pos1 >= down:
        pos1 += pos
    else:
        ansflg = False
        break

pos2 = 0
if ansflg:
    while backward:
        down, pos = heapq.heappop(backward)
        if pos2 >= down:
            pos2 += pos
        else:
            ansflg = False
            break

if pos1 != pos2:
    ansflg = False

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

Solution (Python):
n = int(input())
left = []
right = []
for i in range(n):
    s = input()
    n0 = 0
    n1 = 0
    l = len(s)
    for j in range(l):
        if s[j] == "(":
            n0 += 1
        else:
            if n0 == 0:
                n1 += 1
            else:
                n0 -= 1
    if n0 > 0 or n1 > 0:
        if n0 >= n1:
            left.append([n1, n0])
        else:
            right.append([n0, n1])
 
left.sort()
right.sort()
 
def solve():
    nl0 = 0
    nl1 = 0
    for p in left:
        if p[0] > nl0:
            return False
        nl0 -= p[0]
        nl0 += p[1]
    nr0 = 0
    nr1 = 0
    for p in right:
        if p[0] > nr1:
            return False
        nr1 -= p[0]
        nr1 += p[1]
    if nl0 == nr1:
        return True
    else:
        return False
 
if solve():
    print("Yes")
else:
    print("No")

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 998244353
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
S = inputSLs(N)


is_start = 0
is_end = 0
is_both = 0

data_s = []
data_m = []

for item in S:
  if item[0] == "(" and item[-1] == ")":
    is_both += 1
  elif item[0] == "(":
    is_start += 1
  elif item[-1] == ")":
    is_end += 1
  s = 0
  m = 0
  for i in item:
    if i == "(":
      s += 1
    else:
      s -= 1
      m = min(s,m)
  data_s.append(s)
  data_m.append(m)

    
def final():
  A = []
  B = []
  C = []
  D = []
  for i in range(N):
    s = data_s[i]
    m = data_m[i]
    if m == 0 and s>=0:
      A.append(s)
    elif m < 0 and s>=0:
      B.append([m,s])
    elif m<0 and m<s<0:
      C.append([s-m,s])
    else:
      D.append(s)

  B.sort(reverse=True)
  C.sort()
  
  left = sum(A)
  right = -sum(D)
  
  for item in B:
    left += item[0]
    if left<0:
      return "No"
    left -= item[0]
    left += item[1]
  for item in C:
    right -= item[0]
    if right<0:
      return "No"
    right += item[0]
    right -= item[1]
  return "Yes"
      

if sum(data_s) == 0:
  if is_start>0 and is_end >0:
    print(final())
    exit()
  elif is_start == 0 and is_end >0:
    if is_both >= 1:
      print(final())
      exit()
  elif is_start > 0 and is_end ==0:
    if is_both >= 1:
      print(final())
      exit()
  else:
    if is_both >= 2:
      print(final())
      exit()    
print("No")

Solution (Python):
def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

def cle(x):
	return -x[1]		
couples = [[i,val[i]] for i in milieu]
couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)







def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")

Solution (Python):
n = int(input())

a = []
b = []
for i in range(n):
    s = input()
    x = 0
    y = 0
    for c in s:
        if c == '(':
            y += 1
        else:
            if y >= 1:
                y -= 1
            else:
                x += 1
    if x < y: a.append([x, abs(x-y)])
    else: b.append([y, abs(x-y)])

def calc(a):
    ret = 0
    for x, y in sorted(a):
        if ret < x: return -1
        ret += y
    return ret
   
res1 = calc(a)
res2 = calc(b)
print("Yes" if res1 >= 0 and res1 == res2 else "No")

Solution (Python):
n = int(input())
s = [input() for _ in range(n)]

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in mr:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()

Solution (Python):
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
pgomi = []
mgomi = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 1)
    check = True
    kosu += len(s[i])
    moi = 0
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        moi += p
        dp[i][j+1] = dp[i][j] + p
    saisyo = min(dp[i])
    if saisyo >= 0:plus.append(i)
    elif saisyo == dp[i][-1]:minas.append(i)
    elif dp[i][-1] >= 0:pgomi.append([moi,i])
    else:mgomi.append([moi,i])
pgomi.sort(reverse = True)
mgomi.sort(reverse = True)
ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + [v[1] for v in pgomi] + [v[1] for v in mgomi] + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
else:
    print("Yes")

Solution (Python):
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))


def main():
	N = int(input())	
	L = []
	Slist1 = []
	Slist2 = []
	R = []
	l = 0; r = 0
	for i in range(N):
		M = 0; end = None
		var = 0
		S = input()
		for j in S:
			if j == "(":
				var += 1
				l += 1
			else:
				var -= 1
				r += 1
			M = min(var, M)

		end = var
		if M == 0:
			L.append([M, end])
		elif M == end:
			R.append([M, end])
		elif M < 0 and end > 0:
			Slist1.append([-M, end])
		else:
			Slist2.append([M - end, M, end])
	
	Slist1 = sorted(Slist1)
	Slist2 = sorted(Slist2)
	if l != r:
		print("No")
		return

	cnt = 0
	X = len(L)
	for i in range(X):
		cnt += L[i][1]

	judge = "Yes"
	X = len(Slist1)
	for i in range(X):
		M = Slist1[i][0]
		cnt -= M
		if cnt < 0:
			judge = "No"
			break
		else:
			cnt += M + Slist1[i][1]

	X = len(Slist2)
	for i in range(X):
		cnt += Slist2[i][1]
		if cnt < 0:
			judge = "No"
			break
		else:
			cnt -= Slist2[i][0]

	print(judge)


if __name__ == '__main__':
	main()

Solution (Python):
n = int(input())
brackets_plus = []
brackets_minus = []
right = 0
left = 0
for i in range(n):
    s = input()
    cur = 0
    m = 0
    for j in range(len(s)):
        if s[j] == "(":
            left += 1
            cur += 1
        else:
            right += 1
            cur -= 1
            m = min(m,cur)
    if cur >= 0:
        brackets_plus.append((m,cur))
    else:
        brackets_minus.append((m,cur,m-cur))
if right != left:
    print("No")
    exit()
cur = 0
brackets_plus.sort(reverse = True)
for i in brackets_plus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur += i[1]
brackets_minus.sort(key = lambda x:x[2])
for i in brackets_minus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur += i[1]
print("Yes")

Solution (Python):
N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
if ans:
    for m,t in B:
        if totB + m < 0:
            ans = False
            break
        totB += t
    if totA != totB:
        ans = False

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

Solution (Python):
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(N)]


def solve():
    diffs = []
    max_downs = []
    for s in S:
        diff = 0
        mi = 0
        for c in s:
            diff += 1 if c == '(' else -1
            mi = min(diff, mi)
        diffs.append(diff)
        max_downs.append(-mi)

    if sum(diffs) != 0:
        return False

    positives = []
    zeros = []
    negatives = []
    for i, d in enumerate(diffs):
        if d > 0:
            positives.append((max_downs[i], d, i))
        elif d < 0:
            negatives.append(((-max_downs[i] - d), d, i))
        else:
            zeros.append((max_downs[i], d, i))

    positives.sort()
    zeros.sort()
    negatives.sort()
    pos = 0
    for down, diff, i in positives:
        if down > pos:
            return False
        pos += diff
    for down, diff, i in zeros:
        if down > pos:
            return False
        pos += diff
    for down, diff, i in negatives:
        pos += diff
        down = -down
        if down > pos:
            return False

    assert pos == 0
    return True


ok = solve()
if ok:
    print('Yes')
else:
    print('No')

Solution (Python):
n=int(input())
lipp = []
lipm = []
limm = []
allcnt = 0
for _ in range(n):
    s = input()
    cnt = 0
    mi = 0
    for x in s:
        if x == ')':
            cnt -= 1
            mi = min(mi,cnt)
        else:
            cnt += 1
    if mi == 0:
        lipp.append(cnt)
    elif cnt >= 0:
        lipm.append([mi,cnt])
    else:
        limm.append([cnt - mi, mi,cnt])
    allcnt += cnt
if allcnt != 0:
    print('No')
    exit()

now = sum(lipp)
lipm.sort(reverse = True)
limm.sort()

for mi, cnt in lipm:
    if mi + now < 0:
        print('No')
        exit()
    now += cnt

cnt2 = 0
for sa, mi, cnt in limm:
    if sa > cnt2:
        print('No')
        exit()
    cnt2 += -cnt
print("Yes")

Solution (Python):
n = int(input())
bra = []
ket = []
c = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    bra.append([-mini,now])
  c.append(now)
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    ket.append([-mini,now])  
check = 0
for x in c:
  
  check += x
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
n = len(bra)

import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)

ket.sort()
now = 0
here = -1
n = len(ket)

pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)
print('Yes')

Solution (Python):
N = int(input())
S = [input() for _ in range(N)]

def solve() :
  T = []
  for s in S :
    open = 0
    close = 0
    for c in s :
      if c == ')' :
        if open > 0 :
          open -= 1
        else :
          close += 1
      else :
        open += 1
    T.append((open, close))
  
  if sum(op - cl for op, cl in T) != 0 :
    return 'No'
  
  inc = []
  dec = []
  for op, cl in T :
    if op >= cl :
      inc.append((cl, op))
    else :
      dec.append((op, cl))
      
  inc.sort()
  open = 0
  for cl, op in inc :
    if open >= cl :
      open += op - cl
    else :
      return 'No'
  
  close = 0
  dec.sort()
  for op, cl in dec :
    if close >= op :
      close += cl - op
    else :
      return 'No'
      
  return 'Yes'
      
print(solve())

Solution (Python):


import sys






















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    l_p_only = []
    r_p_only = []
    r_p_l_p = []
    for _ in range(n):
        s = input()
        left_cnt = 0
        right_cnt = 0
        for char in s:
            if char == ')':
                if left_cnt > 0:
                    left_cnt -= 1
                else:
                    right_cnt += 1
            else:
                left_cnt += 1
        if left_cnt == 0 and right_cnt == 0:
            pass
        elif right_cnt == 0:
            l_p_only.append(left_cnt)
        elif left_cnt == 0:
            r_p_only.append(- right_cnt)
        else:
            r_p_l_p.append([- right_cnt, left_cnt])
    
    
    

    current_left = sum(l_p_only)
    pos = []
    neg = []
    for elm in r_p_l_p:
        if elm[0] + elm[1] >= 0:
            pos.append(elm)
        else:
            neg.append(elm)
    pos.sort(key=lambda x: x[0], reverse=True)    
    for elm in pos:
        current_left += elm[0] 
        if current_left >= 0:
            current_left += elm[1]
        else:
            print('No')
            exit()
    neg.sort(key=lambda x: x[0])    
    for elm in neg:
        current_left += elm[0]
        if current_left >= 0:
            current_left += elm[1]
        else:
            print('No')
            exit()
    if current_left >= 0 and current_left == - sum(r_p_only):
        print('Yes')
    else:
        print('No')



if __name__ == "__main__":
    main()

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline 

n = int(input())
s = read().split()

dp = []
dn = []
for i in s:
    a = 0
    d = 0
    for j in i:
        if j == "(": d+= 1
        else: d -= 1
        if d < a: a = d
    
    
    if d >= 0:    
        dp.append((a,d))
    else:
        dn.append((a-d,-d))
    
dp.sort()
dn.sort()

def check(dp):
    D = 0
    while dp:
        a,d = dp.pop()
        if D+a < 0: return False
        D += d
    return [D]



a = check(dp)
b = check(dn)


if a==False or b==False:
    print("No")
else:
    if a[0] != b[0]:
        print("No")
    else:
        print("Yes")