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: Accepted

Solution code:
def scan(s):
    m = 0
    a = 0
    for c in s:
        if c == '(':
            a += 1
        elif c == ')':
            a -= 1
        m = min(m, a)
    return m, a


def key(v):
    m, a = v
    if a >= 0:
        return 1, m, a
    else:
        return -1, a - m, a

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

c = 0
for m, a in sorted([scan(s) for s in S], reverse=True, key=key):
    if c + m < 0:
        c += m
        break
    c += a

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

Submission status: Accepted

Solution code:
n = int(input())
s=['' for _ in range(n)]
for i in range(n):
    s[i]=input()
#x=[[0,0] for _ in range(n)]
hp,hm=0,0
p=[]
m=[]
for i in range(n):
    t=s[i]
    lv=0
    mn=0
    for u in t:
        if u == '(':
            lv+=1
        elif u == ')':
            lv-=1
        mn=min(mn,lv)
    #x[i][0],x[i][1]=lv,mn
    if lv>=0:
        p.append([lv,mn])
        hp+=lv
    else:
        lv*=-1
        m.append([lv,mn+lv])
        hm+=lv
if hp!=hm:
    print('No')
    exit()
p.sort(key=lambda x: x[1],reverse=1)
m.sort(key=lambda x: x[1],reverse=1)
h=0
lv,mn=0,0
for a,b in p:
    lv+=a
    mn+=b
    if mn<0:
        print('No')
        exit()
    mn=lv
lv,mn=0,0
for a,b in m:
    lv+=a
    mn+=b
    if mn<0:
        print('No')
        exit()
    mn=lv
print('Yes')

#print(lv,mn)

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=[list(input()) for i in range(n)]
L1=[]
L2=[]
for i in range(n):
  ct3=0
  l=[0]
  for j in s[i]:
    if j=='(':
      ct3+=1
      l.append(ct3)
    else:
      ct3-=1
      l.append(ct3)
  if l[-1]>=0:
    L1.append((min(l),l[-1]))
  else:
    L2.append((min(l)-l[-1],-l[-1]))

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

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

if ct4!=ct5:
  print('No')
  sys.exit()

print('Yes')

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

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



    n = int(input())
    minsum = [None] * n # (min, sum)
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
N = int(input())

#INF = float('inf')

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)
#print(L,R)

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:

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')

Submission status: Accepted

Solution code:
# Hello from https://codeforces.com/gym/101341/problem/A

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"

Submission status: Accepted

Solution code:
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:   # s==')'
            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')

Submission status: Accepted

Solution code:
# F - Bracket Sequencing

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')

Submission status: Accepted

Solution code:
# F - Bracket Sequencing

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')

Submission status: Accepted

Solution code:
n = int(input())
scop = [] #高低差,min値
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")

Submission status: Accepted

Solution code:
n = int(input())
scop = [] #高低差,min値
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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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 := 始点 < 終点
S1 = []
# S2 := 始点 => 終点
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():
    # Sの終点を合計して0じゃなかったら、終わり
    if sum([s[1] for s in S1]) + sum([s[1] for s in S2]) != 0:
        print("No")
        return
    # S1の中で、最小値が大きい順に並べる
    X1 = sorted(S1, key=lambda x: x[2], reverse=True)
    # S2の中で、最小値が小さい順に並べる
    X2 = sorted(S2, key=lambda x: x[2]-x[1])
    T = 0
    # X1を並べきった後に、X2を並べて実現可能か調べる、終点を合計して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()

Submission status: Accepted

Solution code:
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

    # r-lの大きい順
    ls_plus.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls_plus.sort(key=lambda x: x[0])

    # l-rの小さい順
    ls_minus.sort(key=lambda x: x[0] - x[1])
    # lの大さい順
    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()

Submission status: Accepted

Solution code:
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

    # r-lの大きい順
    ls_plus.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls_plus.sort(key=lambda x: x[0])

    # l-rの小さい順
    ls_minus.sort(key=lambda x: x[0] - x[1])
    # lの大さい順
    ls_minus.sort(key=lambda x: x[0], reverse=True)

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

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

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

    print("Yes")


main()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline


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()

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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')