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:
#!/usr/bin/env python3

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

n = I()
s = [input() for _ in range(n)]
x = [] #(の方が多いもの
y = [] #)の方が多いもの
for i in range(n):
    cnt1 = 0
    cnt2 = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt1 += 1
        else:
            cnt2 += 1
    if cnt1 - cnt2 > 0:
        x.append([cnt2, cnt1, s[i]])
    else:
        y.append([cnt1, cnt2, s[i]])
x.sort() #)が少ない順
y.sort(reverse=True) #(が多い順
tmp = 0
que = deque()
for i, j, k in x:
    for l in k:
        if l == '(':
            tmp += 1
        else:
            if tmp > 0:
                tmp -= 1
            else:
                print('No')
                quit()
for i, j, k in y:
    for l in k:
        if l == '(':
            tmp += 1
        else:
            if tmp > 0:
                tmp -= 1
            else:
                print('No')
                quit()
if tmp != 0:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
dicpos = {}
dicneg = {}

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

Submission status: Accepted

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
exlr.sort()
# exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Accepted

Solution code:
N = int(input())

memo1 = []
memo2 = []
memo3 = []
memo4 = []
for i in range(N):
  S = input()
  sum_n = sum([1 if s=='(' else -1 for s in S])
  if sum_n >= 0:
    sum_n = 0
    min_n = 1
    for s in S:
      if s == ')':
        sum_n -= 1
        min_n = min(min_n, sum_n)
      else:
        sum_n += 1
    if min_n >= 0:
      memo1.append([min_n, sum_n])
    else:
      memo2.append([min_n, sum_n])
  else:
    sum_n = 0
    min_n = 1
    for s in S[::-1]:
      if s == '(':
        sum_n -= 1
        min_n = min(min_n, sum_n)
      else:
        sum_n += 1
    if min_n >= 0:
      memo4.append([min_n, sum_n])
    else:
      memo3.append([min_n, sum_n])

left = 0
for min_n, sum_n in memo1:
  left += sum_n

memo2.sort(reverse=True)
for min_n, sum_n in memo2:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    left += sum_n

right = 0
for min_n, sum_n in memo4:
  right += sum_n

memo3.sort(reverse=True)
for min_n, sum_n in memo3:
  if right + min_n < 0:
    print('No')
    quit()
  else:
    right += sum_n

if left == right:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
n = int(input())
left = []
midplus = []
midzero = []
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:
            midplus.append((r, l))  # a,b-a
        elif l == r:
            midzero.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]

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

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

print('Yes')

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

Submission status: Accepted

Solution code:
n = int(input())
left = []
mid = []
zero = []
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))  # a,b-a
        elif l == r:
            zero.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[1])
mid += zero + midminus

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

print('Yes')

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

tozan = []
gezan = []

def check():
    s = input()
    m = 0
    res = 0
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res = min(res,m)
    if m >= 0:
        tozan.append([res,m])
    else:
        gezan.append([res-m,res,m])

N = int(input())
for _ in range(N):
    check()

tozan.sort(reverse=True)
gezan.sort()
##print(tozan,gezan)
b = 0

for res,m in tozan:
    if b + res < 0:
        print("No")
        exit()
    b += m

for _,res,m in gezan:
    if b + res < 0:
        print("No")
        exit()
    b += m

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def resolve():
    n = int(input())
    positive, negative = [], []
    for _ in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        if balance > 0:
            positive.append((min_balance, balance))
        else:
            negative.append((min_balance, balance))


    now = 0
    # positive は min_balance の大きい方から足せば良い
    positive.sort(reverse = 1)
    for min_balance, balance in positive:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    # negative は sort を工夫
    def cmp(s1, s2):
        m1, b1 = s1
        m2, b2 = s2
        return -1 if min(m1, b1 + m2) > min(m2, b2 + m1) else 1

    negative.sort(key = cmp_to_key(cmp))
    for min_balance, balance in negative:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    print("Yes" if now == 0 else "No")
resolve()

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for i in range(n)]
ruiseki = [[None] * (len(s[i]) + 1) for i in range(n)]

for i in range(n):
    ruiseki[i][0] = 0
    for j, char in enumerate(s[i]):
        if char == "(":
            ruiseki[i][j + 1] = ruiseki[i][j] + 1
        else:
            ruiseki[i][j + 1] = ruiseki[i][j] - 1


first = []
second = []
now_m = 0
now_s = 0
for i in range(n):
    min_, sum_ = min(ruiseki[i]), ruiseki[i][-1]
    if sum_ > 0:
        first.append((min_, sum_))
    else:
        second.append((min_, sum_))

now_m = 0
now_s = 0

first = sorted(first, reverse=True)
for mi, su in first:
    if now_s + mi < 0:
        print("No")
        exit()
    now_s += su

second = sorted(second, key=lambda x: x[0] - x[1])
for mi, su in second:
    if now_s + mi < 0:
        print("No")
        exit()
    now_s += su

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

Submission status: Accepted

Solution code:
n = int(input())
s = []
for i in range(n):
    a = input()
    b = []
    for j in range(len(a)):
        if a[j]=='(':
            b.append(1)
        else:
            b.append(-1)
    s.append(b)

l = []
r = []
for x in s:
    b = 0
    c = 0
    for y in x:
        c+=y
        b = min(b,c)
    z = len(x)
    d = 0
    e = 0
    for j in range(z):
        e += x[z-j-1]
        d = max(d,e)
    if c>0:
        l.append([b,c])
    else:
        r.append([d,c])
l.sort(reverse=True)
r.sort()

flag = 1
x = 0
for b,c in l:
    if x+b<0:
        flag = 0
    x += c

y = 0
for d,c in r:
    if y+d>0:
        flag = 0
    y += c

if y+x!=0:
    flag = 0
print('Yes' if flag else'No')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    b = []
    for s in S:
        bottom = 0
        cur = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            bottom = min(bottom, cur)
        b.append((bottom, cur))

    bp = [_ for _ in b if _[1] > 0]
    bn = [_ for _ in b if _[1] <= 0]
    bp.sort(key=lambda x: x[0], reverse=True)
    bn.sort(key=lambda x: x[1]-x[0], reverse=True)

    cur = 0
    for bt, ct in bp:
        if cur + bt < 0:
            return 'No'
        cur += ct

    for bt, ct in bn:
        if cur + bt < 0:
            return 'No'
        cur += ct

    if cur != 0:
        return 'No'
    return 'Yes'



def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
ss =[]
for _ in range(n):
    ss.append(input())
cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))
 
 
cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[1]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        sys.exit()
    num += left
if(num==0):
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
n = int(input())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

minus = []
plus = []
while si:
    a, b = si.pop()
    if a <= b:
        plus.append((a, b))
    else:
        minus.append((b, a))

plus.sort()
minus.sort()
countl = 0
for a, b in plus:
    if countl >= a:
        countl += b-a
    else:
        print("No")
        sys.exit()

countr = 0
for a, b in minus:
    if countr >= a:
        countr += b-a
    else:
        print("No")
        sys.exit()


if countr == countl:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

tozan = []
gezan = []

def check():
    s = input()
    m = 0
    res = 0
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res = min(res,m)
    if m >= 0:
        tozan.append([res,m])
    else:
        gezan.append([res-m,-m])

N = int(input())
for _ in range(N):
    check()

tozan.sort(reverse=True)
gezan.sort(reverse=True)

t = 0
g = 0

for res,m in tozan:
    if t + res < 0:
        print("No")
        exit()
    t += m

for res,m in gezan:
    if g + res < 0:
        print("No")
        exit()
    g += m

if t == g:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#かっこ列とは…( = +1 ) = -1「途中でマイナスにならない」
N = int(input())
AllMinPlus = []
AllMinMinus = []
AllMinZero = []
for n in range(N):
    S = input()
    minkakko = 10000000
    cur = 0
    for s in S:
        if s == "(":
            cur += 1
        else:
            cur -= 1
        minkakko = min(minkakko,cur)
    if cur >= 0:
        AllMinPlus.append((cur,minkakko))
    elif cur == 0:
        AllMinZero.append((cur,minkakko))
    else:
        AllMinMinus.append((cur,minkakko))
AllMinPlus.sort(key = lambda x:x[1],reverse=True)
AllMinMinus.sort(key = lambda x:x[0]-x[1],reverse=True)
AllMin = AllMinPlus + AllMinZero + AllMinMinus

if sum([x[0] for x in AllMin]) == 0:
    pos = 0
    for a,m in AllMin:
        if pos < -m:
            print("No")
            exit()
        pos += a
        if pos < 0:
            print("No")
            exit()        
    #プラス組のなかでMinが大きい順に積んでいく
    #マイナス組のなかでMinが小さい順に積んでいく
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
s = [0] * n
inc = []
zeros = []
dec = []

for i in range(n):
    s[i] = input()
    start = 0
    minimum = 0
    now = 0
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        minimum = min(minimum, now)
    end = now
    
    if end == 0:
        zeros.append((minimum, i))
    elif start < end:
        inc.append((minimum, i))
    else:
        minimum = minimum - end
        dec.append((minimum, i))

inc.sort(reverse=True)
dec.sort()


now = 0
for (m, i) in inc:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()
        
for (m, i) in zeros:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()

for (m, i) in dec:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()

if now != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    ss=[SI() for _ in range(n)]
    ms1=[]
    ms2=[]
    for s in ss:
        mn=0
        now=0
        for c in s:
            if c=="(":now+=1
            else:now-=1
            if now<mn:mn=now
        if now>0:ms1.append((mn,now))
        else:ms2.append((mn-now,-now))
    #print(ms1)
    #print(ms2)

    cnt=0
    for mn,s in sorted(ms1,reverse=True):
        if cnt+mn<0:
            print("No")
            exit()
        cnt+=s

    cnt2=0
    for mn,s in sorted(ms2,reverse=True):
        if cnt2+mn<0:
            print("No")
            exit()
        cnt2+=s

    if cnt==cnt2:print("Yes")
    else:print("No")

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    plus = []
    minus = []
    total = 0
    for _ in range(N):
        s = input().strip()
        h = 0
        bottom = 0
        for ss in s:
            if ss == "(":
                h += 1
            else:
                h -= 1
                bottom = min(bottom, h)
        total += h
        if h > 0:
            plus.append((bottom, h))
        else:
            minus.append((bottom-h, -h))
    if total != 0:
        print("No")
        sys.exit()
    plus.sort(reverse=True)
    minus.sort(reverse=True)
    height = 0
    for b, h in plus:
        if height + b < 0:
            print("No")
            sys.exit()
        height += h
    height = 0
    for b, h in minus:
        if height + b < 0:
            print("No")
            sys.exit()
        height += h
    print("Yes")
        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def resolve():
    n = int(input())
    first, second, third = [], [], []
    for _ in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        if min_balance == 0:
            first.append((min_balance, balance))
        elif balance > 0:
            second.append((min_balance, balance))
        else:
            third.append((min_balance, balance))

    now = 0
    # first は何も考えず足せば良い
    for min_balance, balance in first:
        now += balance

    # second は min_balance の大きい方から足せば良い
    second.sort(reverse = 1)
    for min_balance, balance in second:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    # third は sort を工夫
    def cmp(s1, s2):
        m1, b1 = s1
        m2, b2 = s2
        return -1 if min(m1, b1 + m2) > min(m2, b2 + m1) else 1

    third.sort(key = cmp_to_key(cmp))
    for min_balance, balance in third:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    print("Yes" if now == 0 else "No")
resolve()

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



n = int(input())

lr = []

for i in range(n):
    s = input()
    m = len(s)
    #exam left
    count = 0
    left = 0
    for j in range(m):
        if(s[j]=='('):
            count += 1
        else:
            if(count == 0):
                left+=1
            else:
                count -=1
    #exam right
    count = 0
    right = 0
    for j in range(m):
        if(s[m-j-1]==')'):
            count += 1
        else:
            if(count == 0):
                right+=1
            else:
                count -=1

    #print(left,right)
    lr.append([left,right])

existL = 0
existR = 0
sumL = 0
sumR = 0
for i in range(n):
    sumL += lr[i][0]
    sumR += lr[i][1]
    if(lr[i][0]==0 and lr[i][1]!=0):
        existL=1
        #print(lr[i])
    if(lr[i][1]==0 and lr[i][0]!=0):
        existR=1
        #print(lr[i])
lr2 = []
for i in range(n):
    if(lr[i][0]==0): lr2.append(lr[i])
lr3 = []
for i in range(n):
    if(lr[i][0]*lr[i][1]!=0): lr3.append(lr[i])
lr3.sort(key = lambda x : x[0]-x[1])
for i in lr3:
    lr2.append(i)
for i in range(n):
    if(lr[i][1]==0): lr2.append(lr[i])
#print(lr2)

ok = 1
now = 0
for i in range(n):
    now -= lr2[i][0]
    if(now<0):
        ok = 0
        #print('a',lr2[i])
    now += lr2[i][1]
    
if(existL*existR == 1 and sumL == sumR and ok==1):
    print("Yes")
else:
    if(sumL==0 and sumR==0):
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for _ in range(N)]
B1 = []
B2 = []
for s in S:
    ncl = nop = 0
    for c in s:
        if c=='(':
            nop+=1
        else:
            if nop>0: nop-=1
            else: ncl+=1

    if nop-ncl>=0:
        B1.append((nop, ncl))
    else:
        B2.append((nop, ncl))

#print(B)
    
Bl = sorted(B1, key=lambda x:x[1])
Br = sorted(B2, key=lambda x:x[0])

xl = 0
for nop, ncl in Bl:
    if ncl>xl:
        print('No')
        exit()
    xl+=nop-ncl

xr = 0
for nop, ncl in Br:
    if nop>xr:
        print('No')
        exit()
    xr+=ncl-nop

print('Yes' if xl==xr else 'No')

Submission status: Accepted

Solution code:
# ()の問題は折れ線で捉えると良い

N = int(input())
ls = [] # 増減が正のもの(0を含む)
rs = [] # 増減が負のもの

tot = 0
for i in range(N):
    s = input()
    h = 0
    b = 0
    for c in s:
        if c == "(":
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h >= 0:
        # 折れ線に対して上っていく奴ら
        ls.append([b, h])
    else:
        # 折れ線に対して下っていく奴ら
        # 右から(hから見るので、最下点は-hする)
        rs.append([b-h, -h])
    tot += h

ls.sort(key = lambda x:x[0], reverse=True)
rs.sort(key = lambda x:x[0], reverse=True)

def check(s):
    h = 0
    for p in s:
        if h+p[0] < 0:
            return False
        h += p[1]
    return True

if check(ls) and check(rs) and tot == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
n = int(input())
si = []
for _ in range(n):
    s = input()
    l = 0
    r = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "(":
            count += 1
        else:
            count = max(0, count-1)
    l = count
    count = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] == ")":
            count += 1
        else:
            count = max(0, count-1)
    r = count
    si.append((l, r))

if len(si) == 1:
    if si[0] == (0, 0):
        print("Yes")
        sys.exit()

index_l = -1
index_r = -1
maxi_l = 0
maxi_r = 0
for i in range(n):
    a, b = si[i]
    if a == 0:
        if maxi_l < b:
            maxi_l = b
            index_l = i
    if b == 0:
        if maxi_r < a:
            maxi_r = a
            index_r = i


count = 0
if index_r < index_l:
    count += si.pop(index_l)[1]
    last = si.pop(index_r)
else:
    last = si.pop(index_r)
    count += si.pop(index_l)[1]

minus = []
plus = []
while si:
    a, b = si.pop()
    if a <= b:
        plus.append((a, b))
    else:
        minus.append((a, b))

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

for a, b in plus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

for a, b in minus:
    if count >= a:
        count += b-a
    else:
        print("No")
        sys.exit()

count -= last[0]

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

Submission status: Accepted

Solution code:
def check(pt, brackets):
    brackets.sort(reverse=True)
    for m, t in brackets:
        if pt + m < 0:
            return -1
        pt += t
    return pt


n = int(input())
brackets_p = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
brackets_m = []
pt = 0
mt = 0
for _ in range(n):
    s = input()
    total = 0
    mini = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if total >= 0:
        if mini == 0:
            pt += total
        else:
            brackets_p.append((mini, total))
    else:
        total, mini = -total, mini - total
        if mini == 0:
            mt += total
        else:
            brackets_m.append((mini, total))

pt = check(pt, brackets_p)
mt = check(mt, brackets_m)

if (pt == -1) or (mt == -1) or (pt != mt):
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
N, = map(int, input().split())
import sys;input=sys.stdin.readline
X = []
Y = []
for _ in range(N):
    s = input().strip()
    a, b = 0, 0
    for c in s:
        if c == "(":
            a += 1
        else:
            if a > 0:
                a -= 1
            else:
                b += 1
    if a >= b:
        X.append((a, b))
    else:
        Y.append((b, a))
X.sort(key=lambda x:x[1])
Y.sort(key=lambda x:x[1])

s = 0
for i in range(len(X)):
    a, b = X[i]
    if s >= b:
        s += a-b
    else:
        print("No")
        sys.exit()
s2 = 0
for i in range(len(Y)):
    a, b = Y[i]
    if s2 >= b:
        s2 += a-b
    else:
        print("No")
        sys.exit()
if s == s2:
    print("Yes")
else:
    print("No")