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 sys
n=int(input())
s=[list(input()) for i in range(n)]
L1=[]
L2=[]
ct1=0;ct2=0
for i in range(n):
  ct3=0
  l=[0]
  for j in range(len(s[i])):
    if s[i][j]=='(':
      ct1+=1
      ct3+=1
      l.append(ct3)
    else:
      ct2+=1
      ct3-=1
      l.append(ct3)
  if l[-1]>=0:
    L1.append((min(l),l[-1]))
  else:
    L2.append((min(l)-l[-1],-l[-1]))
if ct1!=ct2:
  print('No')
  sys.exit()

L1.sort()
L1.reverse()
ct4=0
for i in range(len(L1)):
  if ct4+L1[i][0]<0:
    print('No')
    sys.exit()
  ct4+=L1[i][1]

L2.sort()
L2.reverse()
ct5=0
for i in range(len(L2)):
  if ct5+L2[i][0]<0:
    print('No')
    sys.exit()
  ct5+=L2[i][1]

print('Yes')

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s.strip('\n'):
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp = [-m, (s.count("(")-s.count(")"))-m]
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Solution (Python):
n = int(input())
s = []
for _ in range(n):
    s.append(input())
a = []
b = []
c = []
for i in s:
    mi = 0
    tmp = 0
    for j in i:
        if j=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp<mi:
            mi = tmp
    if tmp>0:
        a.append((mi, tmp))
    elif tmp==0:
        b.append((mi, tmp))
    else:
        c.append((mi, tmp))
a.sort(key=lambda x:-x[0])
c.sort(key=lambda x:x[0]-x[1])
tmp = 0
for i, j in a+b+c:
    if tmp+i<0:
        print('No')
        break
    tmp += j
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Solution (Python):
def main():
    import queue
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))



    n = int(input())
    minsum = [None] * n 
    for i in range(n):
        tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
        c = 0
        m = 0
        for item in tmp:
            c += item
            m = min(c, m)
        minsum[i] = (m, sum(tmp))
    minsum.sort()

    if sum(item[1] for item in minsum)!=0:
        print("No")
    else:
        minsum1 = [item for item in minsum if item[1]>=0]
        minsum2 = [(item[0]-item[1], -item[1]) for item in minsum if item[1]<0]
        minsum2.sort()
        c = 0
        for m,s in minsum1[::-1]:
            if c+m>=0:
                c += s
            else:
                print("No")
                return
        c = 0
        for m,s in minsum2[::-1]:
            if c+m>=0:
                c+=s
            else:
                print("No")
                return
        print("Yes")
main()

Solution (Python):
def main():
    import sys
    from collections import deque
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    pq = deque([])
    mq = deque([])
    for n in range(N):
        s = input().strip()
        mini = 0
        dst = 0
        for ss in [1 if ss == '(' else -1 for ss in s]:
            dst += ss
            mini = min(dst, mini)
        
        if dst >= 0:
            pq.append((mini, dst))
        elif dst < 0:
            mq.append((mini - dst, mini, dst))
    pq = sorted(pq, reverse=True)
    mq = sorted(mq)
    p = 0
    for mini, dst in pq:
        if p + mini < 0:
            print('No')
            exit()
        p += dst
    for minimini, mini, dst in mq:
        if p + mini < 0:
            print('No')
            exit()
        p += dst
    if p != 0:
        print('No')
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        height = 0
        bottom = 0
        for c in s:
            if c == "(":
                height += 1
            else:
                height -= 1
                bottom = min(bottom, height)
        if height > 0:
            up_lines.append((bottom, height))
        else:
            down_lines.append((bottom-height, -height))
    up_lines.sort(reverse=True, key=lambda line: line[0])
    down_lines.sort(reverse=True, key=lambda line: line[0])
    left = 0
    for bottom, height in up_lines:
        if left + bottom < 0:
            print("No")
            return
        left += height
    right = 0
    for bottom, height in down_lines:
        if right + bottom < 0:
            print("No")
            return
        right += height
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import namedtuple
Line = namedtuple('Line', ['lowest', 'end'])


def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        now = 0
        lowest = 0
        for c in s:
            if c == "(":
                now += 1
            else:
                now -= 1
                lowest = min(lowest, now)
        if now > 0:
            up_lines.append(Line(lowest, now))
        else:
            down_lines.append(Line(lowest-now, -now))
    up_lines.sort(key=lambda line: -line.lowest)
    down_lines.sort(key=lambda line: -line.lowest)
    left = 0
    for line in up_lines:
        if left + line.lowest < 0:
            print("No")
            return
        left += line.end
        if left < 0:
            print("No")
            break
    right = 0
    for line in down_lines:
        if right + line.lowest < 0:
            print("No")
            return
        right += line.end
        if right < 0:
            print("No")
            break
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
po,ne=[],[]
now=0
for i in range(n):
    p=0
    mp=0
    for j in input():
        p+=(1,-1)[j==")"]
        mp=min(p,mp)
    if mp:
        if p>=0:
            po.append((mp,p))
        else:ne.append((mp-p,-p))
    else:now+=p
po.sort(reverse=1)
ne.sort(reverse=1)
for m,p in po:
    if m+now<0:print("No");exit()
    else:now+=p
nnow=0
for m,p in ne:
    if m+nnow<0:print("No");exit()
    else:nnow+=p
print("Yes" if now==nnow else "No")

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

ctr = [[], []]
for s in X:
    t = [0] * (len(s) + 1)
    for j in range(len(s)):
        t[j + 1] = t[j] + int(s[j] == "(") - int(s[j] == ")")
    if t[-1] > 0:
        ctr[0].append((min(t), t[-1]))
    else:
        ctr[1].append((min(t) - t[-1], -t[-1]))

flag = True
tmp = 0
for i in range(2):
    cur = 0
    for m, c in sorted(ctr[i], reverse=True):
        flag &= cur + m >= 0
        cur += c
    if i == 0:
        tmp = cur
    else:
        flag &= tmp == cur
        
if flag:
    print("Yes")
else:
    print("No")

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



def check(A):
  th = 0 
  for i in range(len(A)):
    b = A[i][0]
    h = A[i][1]
    if th + b < 0:
      return False
    else:
      th += h
  return True
    

L = []
R = []
goukei = 0
for i in range(N):
  temp = str(input())
  b= 0 
  h = 0 
  for j in range(len(temp)):
    if temp[j] == "(":
      h += 1
    else:
      h -= 1
    b = min(b,h)
  if h > 0:
    L.append([b,h])
  else:
    R.append([b-h,-h])
  goukei += h

L.sort(reverse=True)
R.sort(reverse=True)


if check(L) and check(R) and goukei == 0:
  print("Yes")
else:
  print("No")

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    up = 0
    down = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            elif w == e: down += e
            else: mm.append((w,e))
        else: up += e

    mp.sort(reverse=True)
    for w,e in mp:
        if up + w < 0:
            print('No')
            exit(0)
        up += e

    mm.sort(reverse=True)
    for w,e in mm:
        if down - w > 0:
            print('No')
            exit(0)
        down += e


    if up + down == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Solution (Python):
def check(vec):
    if len(vec) == 0:
        return True
    h = 0
    for v in sorted(vec, reverse=True):
        if h + v[0] < 0:
            return False
        h += v[1]
    return True


def parse(brackets):
    m = 0
    f = 0
    for c in brackets:
        if c == "(":
            f += 1
        else:
            f -= 1
        if m > f:
            m = f
    return m, f


def main():
    N = int(input())
    ls = []
    rs = []
    tot = 0
    for _ in range(N):
        m, f = parse(input().strip())
        tot += f
        if f >= 0:
            ls.append([m, f])
        else:
            rs.append([m-f, -f])
    return tot == 0 and check(ls) and check(rs)


if __name__ == "__main__":
    print("Yes" if main() else "No")

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

mem = [0] * N
for i in range(N):
    s = input()
    x = 0
    y = 0
    for j in range(len(s)):
        if s[j] == '(':
            x += 1
        else:
            x -= 1
            y = min(x, y)
    mem[i] = (x, y)

mem_a = sorted([ele for ele in mem if ele[0] > 0], key=lambda x: -x[1])
mem_b = sorted([ele for ele in mem if ele[0] <= 0], key=lambda x: x[1]-x[0])

ans = True
val = 0
for ele in mem_a:
    if val + ele[1] < 0:
        ans = False
    val += ele[0]
for ele in mem_b:
    if val + ele[1] < 0:
        ans = False
    val += ele[0]


YesNo = lambda tf: print('Yes') if tf else print('No')
YesNo(ans and val == 0)

Solution (Python):

def f():
    N = int(input())
    UP = []
    DOWN = []

    for _ in range(N):
        S = input()
        c = 0
        minC = 0

        for s in S:
            if s == '(':
                c += 1
            else:
                c -= 1
                minC = min(minC, c)

        if c >= 0:
            UP.append((minC, c))
        else:
            DOWN.append((c - minC, c))


    c = 0
    for up in sorted(UP, reverse=True):
        if c + up[0] < 0:
            return False

        c += up[1]

    for down in sorted(DOWN, reverse=True):
        if c + down[1] - down[0] < 0:
            return False

        c += down[1]

    if c != 0:
        return False

    return True


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

Solution (Python):


class BracketString:
    def __init__(self, s, i):
        self.i = i
 
        balance = 0
        minimum = 0
        for c in s:
            if c == "(":
                balance += 1
            else:
                balance -= 1
                minimum = min(minimum, balance)
 
        revBalance = 0
        revMinimum = 0
        for c in reversed(s):
            if c == ")":
                revBalance += 1
            else:
                revBalance -= 1
                revMinimum = min(revMinimum, revBalance)
 
        assert balance == -revBalance
 
        self.balance = balance
        self.minimum = minimum
        self.revMinimum = revMinimum
 
    @staticmethod
    def cmpForPositive(a, b):
        return b.minimum - a.minimum
 
    @staticmethod
    def cmpForNegative(a, b):
        return a.revMinimum - b.revMinimum
 
 
n = int(raw_input())
positive = []
negative = []
neutral = []
sumBalance = 0
for i in xrange(n):
    s = raw_input()
    bs = BracketString(s, i)
    if bs.balance > 0:
        positive.append(bs)
    elif bs.balance < 0:
        negative.append(bs)
    else:
        neutral.append(bs)
    sumBalance += bs.balance
 
if sumBalance != 0:
    print "No"
    exit()
 
positive.sort(cmp=BracketString.cmpForPositive)
negative.sort(cmp=BracketString.cmpForNegative)
 
ans = []
curBalance = 0
 
for bs in positive + neutral + negative:
    if curBalance + bs.minimum < 0:
        print "No"
        exit()
    curBalance += bs.balance
    ans.append(bs.i + 1)
 
print "Yes"

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

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack:
                if stack[-1] == ')':
                    stack.append('(')
                    l = 1
                else:
                    stack.append('(')
                    l += 1
            else:
                stack.append('(')
                l = 1
        else:   
            if stack:
                if stack[-1] == '(':
                    stack.pop()
                    l -= 1
                else:
                    stack.append(')')
                    r += 1
            else:
                stack.append(')')
                r = 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, r)
        min_revl = min(min_revl, l)

if min_revr == 10**20:
    min_revr = 0
if min_revl == 10**20:
    min_revl = 0

if left+rev_l == rev_r+right and left >= min_revr and right >= min_revl:
    print('Yes')
else:
    print('No')

Solution (Python):


from itertools import chain

n = int(input())
ss = [input() for i in range(n)]

def parse(s):
    "バランスしていない閉じ括弧数, 開き括弧数"
    cl, op = 0, 0
    for c in s:
        if c == '(':
            op += 1
        elif op > 0:
            op -= 1
        else:
            cl += 1
    return (cl, op)

inc   = []  
dec   = []  
close = []  
for s in ss:
    cl, op = parse(s)
    if cl < op:
        inc.append((cl, op))
    elif op == 0:
        close.append((cl, op))
    else:
        dec.append((cl, op))
peak = 0
inc.sort()
dec.sort(reverse=True)
for cl, op in chain(inc, dec, close):
    if peak < cl:
        print('No')
        exit()
    peak += op - cl
print('Yes' if peak == 0 else 'No')

Solution (Python):


from itertools import chain

n = int(input())
ss = [input() for i in range(n)]

def parse(s):
    "バランスしていない閉じ括弧数, 開き括弧数"
    cl, op = 0, 0
    for c in s:
        if c == '(':
            op += 1
        elif op > 0:
            op -= 1
        else:
            cl += 1
    return (cl, op)

open  = []  
close = []  
inc   = []  
dec   = []  
for s in ss:
    cl, op = parse(s)
    if cl == 0:
        open.append((cl, op))
    elif cl < op:
        inc.append((cl, op))
    elif op == 0:
        close.append((cl, op))
    else:
        dec.append((cl, op))
peak = 0
inc.sort()
dec.sort(reverse=True)
for cl, op in chain(open, inc, dec, close):
    if peak < cl:
        print('No')
        exit()
    peak += op - cl
print('Yes' if peak == 0 else 'No')

Solution (Python):
n = int(input())
scop = [] 
scom = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif not sa == ms:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]

print("Yes")

Solution (Python):
n = int(input())
scop = [] 
scom = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in s:
        if i == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif not sa == ms:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]

print("Yes")

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
chk = []
res = []
for i in range(n):
  s = input().strip()
  m = 0
  e = 0
  for i in s:
    if i == ')':
      e -= 1
      m = min(m,e)
    else:
      e += 1
  if e >= 0:
    chk.append((m,e))
  else:
    res.append((-1*e+m,-1*e))
  
from operator import itemgetter
res.sort(key=itemgetter(0),reverse=True)
chk.sort(key=itemgetter(0),reverse=True)
ans = 'Yes'
st = 0
for i,j in chk:
  if i+st < 0:
    ans = 'No'
    break
  st += j
  
sr = 0
for i,j in res:
  if i+sr < 0:
    ans = 'No'
    break
  sr += j
  
if st != sr:
  ans = 'No'

print(ans)

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

pos = []
neg = []
for s in S:
    sm = 0
    mn = 0
    for c in s:
        if c=='(':
            sm += 1
        else:
            sm -= 1
            mn = min(mn, sm)
    if sm >= 0:
        pos.append((mn,sm))
    else:
        neg.append((mn-sm, -sm))

pos.sort(key=lambda x:-x[0])
neg.sort(key=lambda x:-x[0])

hp = 0
for m,s in pos:
    if hp + m < 0:
        print('No')
        exit()
    hp += s

hn = 0
for m,s in neg:
    if hn + m < 0:
        print('No')
        exit()
    hn += s

print('Yes' if hp==hn else 'No')

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

def cnt(s):
    r = [0] * (len(s)+1)
    for i, v in enumerate(s):
        if v == '(':
            r[i+1] = r[i] + 1
        else:
            r[i+1] = r[i] - 1
    return r[0], r[-1], min(r)


S1 = []

S2 = []
for i in range(N):
    s = input()
    t = tuple(cnt(s))
    if t[1] > 0:
        S1.append(t)
    else:
        S2.append(t)
def main():
    
    if sum([s[1] for s in S1]) + sum([s[1] for s in S2]) != 0:
        print("No")
        return
    
    X1 = sorted(S1, key=lambda x: x[2], reverse=True)
    
    X2 = sorted(S2, key=lambda x: x[2]-x[1])
    T = 0
    
    for s, t, mi in X1:
        if T + mi < 0:
            print("No")
            return
        T += t
    for s, t, mi in X2:
        if T + mi < 0:
            print("No")
            return
        T += t
    print("Yes")

main()

Solution (Python):
def main():
    n = int(input())
    l_0 = []
    r_0 = []
    ls_plus = []
    ls_minus = []
    sum_l = 0
    sum_r = 0
    for i in range(n):
        s = input()
        left, right = 0, 0
        for j in range(len(s)):
            if s[j] == '(':
                right += 1
            else:
                if right > 0:
                    right -= 1
                else:
                    left += 1
        if left == right == 0:
            continue

        if left == 0:
            l_0.append((left, right))
        elif right == 0:
            r_0.append((left, right))
        elif left < right:
            ls_plus.append((left, right))
        else:
            ls_minus.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls_plus) == len(ls_minus) == len(l_0) == len(r_0) == 0:
        print("Yes")
        return

    if len(l_0) == 0 or len(r_0) == 0:
        print("No")
        return
    if sum_l != sum_r:
        print("No")
        return

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

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

    now_r = 0
    for ll in l_0:
        now_r += ll[1]

    for _ in ls_plus:
        r = _[1]
        x = now_r - _[0]
        if x >= 0:
            now_r = x + r
        else:
            print("No")
            return

    for _ in ls_minus:
        r = _[1]
        x = now_r - _[0]
        if x >= 0:
            now_r = x + r
        else:
            print("No")
            return

    print("Yes")


main()

Solution (Python):
def main():
    n = int(input())
    l_0 = []
    r_0 = []
    ls_plus = []
    ls_minus = []
    sum_l = 0
    sum_r = 0
    for i in range(n):
        s = input()
        left, right = 0, 0
        for j in range(len(s)):
            if s[j] == '(':
                right += 1
            else:
                if right > 0:
                    right -= 1
                else:
                    left += 1
        if left == right == 0:
            continue

        if left == 0:
            l_0.append((left, right))
        elif right == 0:
            r_0.append((left, right))
        elif left < right:
            ls_plus.append((left, right))
        else:
            ls_minus.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls_plus) == len(ls_minus) == len(l_0) == len(r_0) == 0:
        print("Yes")
        return

    if len(l_0) == 0 or len(r_0) == 0:
        print("No")
        return
    if sum_l != sum_r:
        print("No")
        return

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

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

    now_r = 0
    for ll in l_0:
        now_r += ll[1]

    
    for i in range(len(ls_plus)):
        
        r = ls_plus[i][1]
        x = now_r - ls_plus[i][0]
        if x >= 0:
            
            now_r = x + r
        else:
            print("No")
            return

    for i in range(len(ls_minus)):
        
        r = ls_minus[i][1]
        x = now_r - ls_minus[i][0]
        if x >= 0:
            
            now_r = x + r
        else:
            print("No")
            return

    print("Yes")


main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        level = 0
        for c in input():
            if c == '(':
                level += 1
            else:
                level -= 1
                depth = min(depth, level)
        if depth >= 0 and level == 0:
            continue
        elif level > 0:
            inc_chunks.append((depth, level))
        else:
            dec_chunks.append((depth - level, -level))

    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, level in inc_chunks:
        if inc_level + depth < 0:
            return 'No'
        inc_level += level
    dec_level = 0
    for depth, level in dec_chunks:
        if dec_level + depth < 0:
            return 'No' 
        dec_level += level
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        level = 0
        for c in input():
            if c == '(':
                level += 1
            else:
                level -= 1
                depth = min(depth, level)
        if level > 0:
            inc_chunks.append((depth, level))
        else:
            dec_chunks.append((depth - level, -level))

    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, level in inc_chunks:
        if inc_level + depth < 0:
            return 'No'
        inc_level += level
    dec_level = 0
    for depth, level in dec_chunks:
        if dec_level + depth < 0:
            return 'No' 
        dec_level += level
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Solution (Python):
import sys



def parse(s):
    bottom = 0
    delta = 0
    for c in s:
        delta += (1 if c == "(" else -1)
        bottom = min(bottom, delta)
    return bottom, delta


def compute(pars):
    pars.sort(reverse=True)
    h = 0
    for bottom, delta in pars:
        if h + bottom < 0:
            print("No")
            sys.exit()
        h += delta
    return h


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

    incs = []
    decs = []
    for _ in range(N):
        bottom, delta = parse(input())
        if delta > 0:
            incs.append((bottom, delta))
        else:
            decs.append((bottom-delta, -delta))

    inc_tot = compute(incs)
    dec_tot = compute(decs)
    if inc_tot == dec_tot:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Solution (Python):
def check(ar):
    h = 0
    for bottom, up in ar:
        if h + bottom < 0:
            return False
        h += up
    return True


if __name__ == "__main__":
    N = int(input())
    pos = []
    neg = []
    equal = 0
    for _ in range(N):
        cnt = 0
        bottom = 0
        for s in input():
            if s == "(":
                cnt += 1
            else:
                cnt -= 1
            bottom = min(bottom, cnt)
        equal += cnt
        if cnt >= 0:
            pos.append((bottom, cnt))
        else:
            cnt = -cnt
            bottom += cnt
            neg.append((bottom, cnt))

    pos.sort(reverse=True)
    neg.sort(reverse=True)
    if check(pos) and check(neg) and equal == 0:
        print("Yes")
    else:
        print("No")

Solution (Python):
import sys
N = int(input())
B1 = []
B2 = []

def change(S):
    MIN = 0
    SUM = 0
    for i in S:
        if i == ')':
            SUM -= 1
            MIN = min(MIN, SUM)
        else:
            SUM += 1
    MIN *= -1
    return (MIN, SUM)

for _ in range(N):
    b = change(input())
    if b[1] > 0:
        B1.append(b)
    else:
        B2.append((b[0] + b[1], b[0], b[1]))

B1.sort()
B2.sort(reverse = True)

cnt = 0
for b in B1:
    if cnt < b[0]:
        print('No')
        sys.exit()
    cnt += b[1]

for b in B2:
    if cnt < b[1]:
        print('No')
        sys.exit()
    cnt += b[2]

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

Solution (Python):
n = int(input())
sp, sm = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, tl = 0, 0
    for i in range(m):
        if s[i] == ')':
            tl -= 1
        else:
            tl += 1
        l = min(l, tl)

    r, tr = 0, 0
    for i in range(m):
        if s[m-1-i] == '(':
            tr -= 1
        else:
            tr += 1
        r = min(r, tr)

    res += tl
    if tl >= 0:
        sp.append((l, tl))
    else:
        sm.append((r, tr))

if res != 0:
    print('No')
    exit()

sp.sort(key=lambda x: -x[0])
sm.sort(key=lambda x: -x[0])


xp = len(sp)
cur = 0
for l, tl in sp:
    if cur + l < 0:
        print('No')
        exit()
    cur += tl

cur = 0
for r, tr in sm:
    if cur + r < 0:
        print('No')
        exit()
    cur += tr

print('Yes')

Solution (Python):

import sys
from bisect import bisect_left,bisect_right
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class SegmentTree:
        def __init__(self,n,segfunc,ide_ele):
            self.segfunc=segfunc
            self.ide_ele=ide_ele
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(len(iter)):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    Seg=SegmentTree(10**6+1,lambda a,b:max(a,b),-INF)
    l_PM=defaultdict(list)
    stack=defaultdict(list)
    minus=set()
    for i,s in enumerate(S):
        p=0
        m=0
        for x in s:
            if x=='(':
                p+=1
            else:
                if p>0:
                    p-=1
                else:
                    m+=1
        if m==0 and p>0:
            P+=p
        elif p==0 and m>0:
            M+=m
        elif p>0 and m>0:
            c+=1
            minus.add(m)
            stack[m].append(p-m)
    
    minus=list(minus)
    minus.sort()
    for x in minus:
        stack[x].sort()
        if x<=P:
            while stack[x]:
                y=stack[x].pop()
                if y>=0:
                    c-=1
                    P+=y
                else:
                    Seg.update(x,y)
                    l_PM[y].append(x)
                    break
        else:
            y=stack[x].pop()
            Seg.update(x,y)
            l_PM[y].append(x)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF or P+x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        res=bisect_right(l_PM[x],P)-1
        index=l_PM[x][res]
        del l_PM[x][res]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
            l_PM[y].append(index)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()