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:
import sys
n=int(input())
a=[]
b=[]
for i in range(n):
  s=input()
  overall=0
  minimum=0
  current=0
  for j in range(len(s)):
    if s[j]=='(':
      current+=1
    else:
      current-=1
    minimum=min(current,minimum)
  overall=current
  if overall>=0:
    a.append([overall,minimum])
  else:
    b.append([overall,minimum])
finalsum=0
a=sorted(a, key=lambda t:t[1])
a.reverse()
b=sorted(b, key=lambda t:t[0]-t[1])
b.reverse()
for i in a:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
for i in b:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
if finalsum==0:
  print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    up, down = [], []
    for _ in range(n):
        s = list(input())
        m = 0
        height = 0
        for si in s:
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if height >= 0:
            up.append([m, height])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([j for i, j in up])-sum([j for i, j in down]) != 0:
        print("No")
        return
    h = 0
    for mi, hi in up:
        if h+mi < 0:
            print("No")
            return
        h += hi
    h = 0
    for hmi, hi in down:
        if h+hmi >= 0:
            h += hi
        else:
            print("No")
            return
    print("Yes")
    
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

N = int(input())

S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append([mim, end])
  else:
    S_n.append([end-mim, end])
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

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

Submission status: Accepted

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
S.sort(key=lambda a: -a[0] - a[1])
S1 = []
S2 = []
for s in S:
    if s[0] + s[1] >= 0:
        S1 += [s]
    else:
        S2 += [s]
S1.sort(key=lambda a: -a[1])
S2.sort(key=lambda a: -a[0])
cnt = 0
for s in S1:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
for s in S2:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
if cnt:
    No()
Yes()

Submission status: Accepted

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
S.sort(key=lambda a: -a[0] - a[1])
S1 = sorted([s for s in S if s[0] + s[1] >= 0], key=lambda a: -a[1])
S2 = sorted([s for s in S if s[0] + s[1] < 0], key=lambda a: -a[0])
cnt = 0
for s in S1:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
for s in S2:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
if cnt:
    No()
Yes()

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for i in range(n)]
l, r = [], []
for i in s:
    a, b = 0, 0
    for j in range(len(i)):
        if i[j] == "(":
            b += 1
        if i[j] == ")":
            if b <= 0:
                a += 1
            else:
                b -= 1
    if b - a > 0:
        l.append([a, b])
    else:
        r.append([a, b])
l.sort(key=lambda x:x[0])
r.sort(key=lambda x:x[1], reverse=True)
li = l + r
ans = 0
for i in li:
    ans -= i[0]
    if ans < 0:
        exit(print("No"))
    ans += i[1]
print("Yes" if ans == 0 else "No")

Submission status: Accepted

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

n = int(input())

plus = []
minus = []
for _ in range(n):
    min_s = 0
    ts = 0
    s = input().strip()
    for c in s:
        ts += 1 if c == '(' else -1
        min_s = min(ts, min_s)
    if ts >= 0:
        plus.append((-min_s, ts))
    else:
        minus.append((-(min_s - ts), -ts))

plus.sort()
minus.sort()

s1 = 0
for m, t in plus:
    if s1 - m < 0:
        print('No')
        exit()
    s1 += t

s2 = 0
for m, t in minus:
    if s2 - m < 0:
        print('No')
        exit()
    s2 += t

if s1 == s2:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc167/submissions/13072107
import sys
readline = sys.stdin.readline

def resolve():
    N = int(readline())
    S = [readline().strip() for i in range(N)]
    L,R = [],[]
    D = []
    for s in S:
        l, r = 0, 0
        for c in s:
            if c == ')':
                if l > 0:
                    l -= 1
                else:
                    r += 1
            else:
                l += 1
        if l == 0 and r == 0:
            pass
        elif l == 0:
            R.append(r)
        elif r == 0:
            L.append(l)
        else:
            D.append((l, r))
    L = sum(L)
    R = sum(R)

    inc = []
    dec = []
    for l,r in D:
        if l > r:
            inc.append((l, r))
        else:
            dec.append((l, r))
    
    inc.sort(key=lambda x:x[1])
    dec.sort(key=lambda x:-x[1])
    
    D = inc + dec
    
    for i, (l,r) in enumerate(D):
        L -= r
        if L < 0:
            print('No')
            exit(0)
        L += l
    
    if L == R:
        print('Yes')
    else:
        print('No')
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n = ri()
    neg_dm = []
    pos_dm = []
    for i in range(n):
        S = input()
        depth = 0
        max_depth = 0
        for c in S:
            if c == '(':
                depth -= 1
            else:
                depth += 1
                max_depth = max(max_depth, depth)
        if depth < 0:
            neg_dm.append([max_depth, depth])
        else:
            pos_dm.append([max_depth, depth])

    neg_dm.sort()
    pos_dm.sort(key = lambda x : [x[1]-x[0], -x[0]])

    # print (neg_dm)
    # print (pos_dm)
    curr_depth = 0
    for m, d in neg_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

    for m, d in pos_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

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


mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().strip()


n=int(input())
A=[]
#
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in input():
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum( [PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")

Submission status: Accepted

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

def main():
  n = int(input())
  
  a = []
  b = []
  for i in range(n):
    s = input()
    c1, c2 = 0, 0
    for i in range(len(s)):
      if s[i] == "(":
        c2 += 1
      if s[i] == ")":
        if c2:
          c2 -= 1
        else:
          c1 += 1
    if c1 >= c2:
      b.append((c2, c1))
    else:
      a.append((c1, c2))
  a.sort()
  b.sort(reverse=True)
  ans = False
  sub = 0
  for value in a:
    k1, k2 = value[0], value[1]
    if sub < k1:
      ans = True
      break
    sub += k2-k1
  for value in b:
    k2, k1 = value[0], value[1]
    if ans or sub < k1:
      ans = True
      break
    sub += k2-k1
  print("No" if ans or sub else "Yes")

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    if n == 0:
        print("Yes")
        return
    slup = []
    sldown = []
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
            else:
                height -= 1
                mi = min(mi, height)
        if height >= 0:
            slup.append([mi, height])
        else:
            sldown.append([mi-height, -height])

    slup.sort(key = lambda x: -x[0])
    sldown.sort(key = lambda x: -x[0])
    if sum([si[1] for si in slup]) + sum([-si[1] for si in sldown]):
        print("No")
        return
    h = 0
    for si in slup:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    h = 0
    for si in sldown:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    print("Yes")
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    if n == 0:
        print("Yes")
        return
    slup = []
    sldown = []
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
            else:
                height -= 1
                mi = min(mi, height)
        if height >= 0:
            slup.append([mi, height])
        else:
            sldown.append([mi-height, -height])

    slup.sort(reverse=True)
    sldown.sort(reverse=True)
    if sum([si[1] for si in slup]) + sum([-si[1] for si in sldown]):
        print("No")
        return
    h = 0
    for si in slup:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    h = 0
    for si in sldown:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    print("Yes")
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()

def resolve():
    def check(arr):
        height = 0
        for b, h in arr:
            if height+b < 0:
                return False
            height += h
        return True

    N = int(inp())
    plus = []
    minus = []
    total = 0
    for _ in range(N):
        # 1つのパーツを処理
        S = inpS()
        cum = 0 # 累積和(最高地点)
        bottom = 0 # 最下地点
        for s in S:
            if s == "(":
                cum += 1
            else:
                cum -= 1
                bottom = min(bottom, cum)

        total += cum
        if cum > 0:
            plus.append((bottom, cum))
        else:
            minus.append((bottom-cum, -cum))

    plus.sort(reverse=True)
    minus.sort(reverse=True)

    if check(plus) and check(minus) and total == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    def check(arr):
        height = 0
        for b, h in arr:
            if height+b < 0:
                return False
            height += h
        return True

    N = int(input())
    plus = []
    minus = []
    total = 0
    for _ in range(N):
        # 1つのパーツを処理
        S = input()
        cum = 0 # 累積和(最高地点)
        bottom = 0 # 最下地点
        for s in S:
            if s == "(":
                cum += 1
            else:
                cum -= 1
            bottom = min(bottom, cum)

        total += cum
        if cum > 0:
            plus.append((bottom, cum))
        else:
            minus.append((bottom-cum, -cum))

    plus.sort(reverse=True)
    minus.sort(reverse=True)

    if check(plus) and check(minus) and total == 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
s = []
for _ in range(n):
    s.append(input())

inc = []
zeros = []
dec = []

for i, j in enumerate(s):
    minimum = 0
    now = 0
    for k in j:
        if k == "(":
            now += 1
        else:
            now -= 1
        minimum = min(minimum, now)
    if now > 0:
        inc.append([minimum, i])
    elif now < 0:
        dec.append([minimum - now, i])
    else:
        zeros.append([minimum, i])

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

now = 0

for i, j in inc:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
for i, j in zeros:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
for i, j in dec:
    for k in s[j]:
        if k == "(":
            now += 1
        else:
            now -= 1
        if now < 0:
            print("No")
            sys.exit()
ans = "Yes" if now == 0 else "No"
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: (- M - z[0] if sum(z)>= 0 else M - z[1])):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Accepted

Solution code:

from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted([x for x in u if sum(x) >= 0], key=lambda z: -z[0]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
for a, b in sorted([x for x in u if sum(x) < 0], key=lambda z: -z[1]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Submission status: Accepted

Solution code:
from collections import deque,defaultdict
import bisect
N = int(input())
S = [input() for i in range(N)]

def bend(s):
    res = 0
    k = 0
    for th in s:
        if th == '(':
            k += 1
        else:
            k -= 1
        res = min(k,res)
    return res

species = [(bend(s),s.count('(')-s.count(')')) for s in S]

ups = [(b,u) for b,u in species if u > 0]
flats = [(b,u) for b,u in species if u == 0]
downs = [(b,u) for b,u in species if u < 0]


ups.sort()
high = 0
for b,u in ups[::-1] + flats:
    if high + b < 0:
        print('No')
        exit()
    high += u

rdowns = [(b-u,-u) for b,u in downs]
rdowns.sort()
high2 = 0
for b,u in rdowns[::-1]:
    if high2 + b < 0:
        print('No')
        exit()
    high2 += u

if high == high2:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n=int(input())
pos=[]
neg=[]
for i in range(n):
    s=input()
    bal=0
    mn=0
    for ch in s:
        if ch=='(':
            bal+=1
        if ch==')':
            bal-=1
        mn=min(mn,bal)
    if -mn<bal-mn:
        pos.append((-mn,bal-mn))
    else:
        neg.append((-mn,bal-mn))
def cmp(it):
    return -it[1]
pos.sort()
neg.sort(key=cmp)
bal=0
ok=True
for (m,b) in pos:
    if bal-m<0:
        ok=False
    bal+=b-m
for (m,b) in neg:
    if bal-m<0:
        ok=False
    bal+=b-m
if bal!=0:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
'''
○ 基本方針
'(' を1上昇、')'を1下降とイメージすると、
この問題は「0未満にならず、最終的に0になるか」と言い換えられる。

1. ／ 型
2. V 型で上昇
3. V型で下降
4. ＼型
の順で使えばよい。

2は、V字の最下点が最も高いものから使うのが最適。（徐々に、大きく沈み込むものを使えるようになる）
3は、(|下降| - V字の最下点) が最も大きいものから使うのが最適。（沈み込みが大きいものは早めに消化する）

ここで、1は2、3は4と合わせて考えて良い。
'''

Yes = 'Yes'
No = 'No'

def main():
    # 入力
    N = int(input())
    up = []     # 上昇が0以上のもの
    down = []   # 上昇が0未満のもの
    for _ in range(N):
        S = input()
        h, b = 0, 0 # h:上昇数、b:最下点
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    # 演算
    up.sort(key=lambda t: t[1], reverse=True)           # 上昇は、最下点が高いものから使う
    down.sort(key=lambda t: t[0]-t[1], reverse=True)    # 下降は、沈み込み後の反転上昇が大きいものから使う
    H = 0   # 現在の高さ
    for h, b in up + down:
        if H+b>=0:  # 高さが0未満にならない条件
            H += h
        else:
            print(No)
            return
    # 出力
    if H == 0:
        print(Yes)
    else:
        print(No)


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    up = []
    down = []
    for _ in range(N):
        S = input()
        h = 0
        b = 0
        for s in S:
            if s=='(':
                h += 1
            else:
                h -= 1
                b = min(b, h)
        #
        if h>=0:
            up.append((h, b))
        else:
            down.append((h, b))
    #
    up.sort(key=lambda t: t[1], reverse=True)
    down.sort(key=lambda t: t[0]-t[1], reverse=True)
    H = 0
    for h, b in up:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    for h, b in down:
        if H+b>=0:
            H += h
        else:
            print(No)
            return
    #
    if H == 0:
        print(Yes)
    else:
        print(No)





main()

Submission status: Accepted

Solution code:
n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
first = ""
last = ""
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = a_count
    bi = b_count

    if ai == 0:
        first += min_s
    elif bi == 0:
        last += min_s
    elif bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

first_list= sorted(first_list, key=lambda s: s[1])
last_list= sorted(last_list, key=lambda s: s[1], reverse=True)

ans = first
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]
ans += last

a_count = 0
b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n = 4
    S = ['((()))', '((((((', '))))))', '()()()']

  else:
    ## INPUT 
    n = int(input())
    #a, b = map(int, input().split())
    S = [input() for _ in range(n)]

  ## SUBMITION CODES HERE
  def CNT(A):
    tmp, Min = 0, 0
    for a in A:
        if a == '(': tmp += 1
        else: tmp -= 1
        Min = min(Min, tmp)
    return (-Min, tmp-Min)
  
  T = [CNT(s) for s in S]

  pls = []
  mis = []
  for l, r in T:
    if l <= r: pls.append((l, r))
    else: mis.append((l, r))

  pls.sort(key=lambda a: a[0])
  mis.sort(key=lambda a: a[1], reverse=True)
  total = pls + mis

  levl = 0
  for l, r in total:
    levl -= l
    if levl < 0:
        print('No')
        exit()
    levl += r

  print('Yes' if levl == 0 else 'No')
    
main()

Submission status: Accepted

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

N = int(readline())
S = [readline().rstrip() for _ in range(N)]

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            st.pop()
    return st.count(')'), st.count('(')

cb_obs = map(count_cb_ob, S)
f, b, s = [], [], []
for down, up in cb_obs:
    (f if down < up else (s if down == up else b)).append((down, up))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    ans = 'No'

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            st.pop()
    return st.count(')'), st.count('(')

cb_obs = list(map(count_cb_ob, S))
f = list(filter(lambda cb_ob: cb_ob[0] < cb_ob[1] , cb_obs))
b = list(filter(lambda cb_ob: cb_ob[0] > cb_ob[1] , cb_obs))
s = list(filter(lambda cb_ob: cb_ob[0] == cb_ob[1] , cb_obs))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    print('No')
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
jsum=0
gjlist=[]
ejlist=[]
esum=0

def jouka(t):
	global jsum
	global gjlist
	global ejlist
	global esum
	
	tmpj=0
	tmpe=0
	
	for i in range(len(t)):
		if t[i] == "(":
			tmpj += 1
		else:
			if tmpj == 0:
				tmpe +=1
			else:
				tmpj -=1
		
	if tmpe == 0:
		jsum += tmpj
	elif tmpj == 0:
		esum += tmpe
	elif tmpj > tmpe:
		gjlist.append([tmpe,tmpj])
	else:
		ejlist.append([tmpe,tmpj])

for j in range(n):
	jouka(input())

gjlist.sort(key=lambda x:x[0])
ejlist.sort(reverse = True,key=lambda x:x[0])

streak=jsum
for gj in gjlist:
	if gj[0] > streak:
		print("No")
		sys.exit()
	else:
		streak += gj[1]-gj[0]

for ej in ejlist:
	if ej[0] > streak:
		print("No")
		sys.exit()
	else:
		streak += ej[1]-ej[0]

if streak == esum:
	print("Yes")
else:
	print("No")

Submission status: Accepted

Solution code:
def count(i, s):
    left = right = 0
    for e in s:
        if e == "(":
            left += 1
        else:
            if left == 0:
                right += 1
            else:
                left -= 1

    return left-right, left, right, i


n = int(input())
S = [input() for i in range(n)]
s1 = []
s2 = []
for i, e in enumerate(S):
    c = count(i, e)
    # print(i, c)
    if c[0] >= 0:
        s1.append((c[2], c[3]))
    else:
        s2.append((-c[1], c[3]))

s1.sort()
s2.sort()
# print(s1, s2)
s = []
for e in s1:
    s.append(S[e[1]])
for e in s2:
    s.append(S[e[1]])
# print(s)

_, left, right, _ = count(0, "".join(s))
if left == right == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
s = []
for i in range(n):
    s.append(input())

ls1 = []
ls2 = []

for item in s:
    stk1 = []
    stk2 = []
    for ch in item:
        if ch == '(':
            stk2.append(ch)
        else:
            if len(stk2) > 0:
                stk2.pop()
            else:
                stk1.append(ch)
    l1 = len(stk1)
    l2 = len(stk2)
    if l2 >= l1:
        ls1.append((l1, l2))
    else:
        ls2.append((l1, l2))


ls1.sort()

cnt = 0

for item in ls1:
    cnt -= item[0]
    if cnt < 0:
        print('No')
        exit()
    else:
        cnt += item[1]

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

for item in ls2:
    cnt -= item[0]
    if cnt < 0:
        print('No')
        exit()
    else:
        cnt += item[1]

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
inc = []
dec = []
for _ in range(n):
    s = readline().rstrip().decode()
    d, r = 0, 0
    for m in s:
        d += (1 if m == '(' else -1)
        r = max(r, -d)
    (dec if d < 0 else inc).append((d, r))
inc.sort(key=lambda x: x[1])
dec.sort(key=lambda x: x[0] + x[1])
p1 = 0
p2 = 0
flag = True
for i in inc:
    flag &= i[1] <= p1
    p1 += i[0]
for d in dec:
    flag &= p2 >= d[0] + d[1]
    p2 -= d[0]
flag &= p1 == p2
print('Yes' if flag else 'No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()

LSTP=[]
LSTN=[]
for i in range(N):
    cnt = 0
    cntMin = 0
    s = input()
    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1
        cntMin = min(cntMin, cnt)
    # print(cntMin)
    if cnt >= 0:
        LSTP.append((cntMin, cnt))
    else:
        LSTN.append((-(cnt-cntMin), -cnt))

LSTP.sort(reverse=True)
LSTN.sort(reverse=True)

res = 0
for cntMin, cnt in LSTP:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

res2 = 0
for cntMin, cnt in LSTN:
    if res2 + cntMin < 0:
        print("No")
        exit(0)
    res2 += cnt

if res - res2 == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def seq_positive(ls):
        state = 0
        for l, st in ls:
            if state+l < 0:
                return False
            state += st
        return True

    # 部分括弧列の特徴量を計算する。
    # 経過中の最小値と、最終到達値
    left_seq = []
    right_seq = []
    total = 0
    for s in S:
        state = 0
        lower = 0
        for c in s:
            if c == "(":
                state += 1
            else:
                state -= 1
            lower = min(lower, state)
        if state > 0:
            left_seq.append((lower, state))
        else:
            right_seq.append((lower-state, -state))
        total += state

    left_seq.sort(reverse=True)
    right_seq.sort(reverse=True)
    # print(left_seq)
    # print(right_seq)

    if seq_positive(left_seq) and seq_positive(right_seq) and total == 0:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()