Problem:
 Score : 600 points    Problem Statement A bracket sequence is a string that is one of the following:   An empty string;  The concatenation of ( , A , and ) in this order, for some bracket sequence A ;  The concatenation of A and B in this order, for some non-empty bracket sequences A and B /   Given are N strings S_i . Can a bracket sequence be formed by concatenating all the N strings in some order?      Constraints  1 \leq N \leq 10^6  The total length of the strings S_i is at most 10^6 .  S_i is a non-empty string consisting of ( and ) .         Input Input is given from Standard Input in the following format:  N  S_1  :  S_N       Output If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes ; otherwise, print No .        Sample Input 1 2
)
(()      Sample Output 1 Yes  Concatenating (() and ) in this order forms a bracket sequence.       Sample Input 2 2
)(
()      Sample Output 2 No       Sample Input 3 4
((()))
((((((
))))))
()()()      Sample Output 3 Yes       Sample Input 4 3
(((
)
)      Sample Output 4 No

Solution (Python):
def main():
    n = int(input())
    s = [list(input()) for _ in range(n)]
    L_cnt = []
    R_cnt = []
    LR_cnt = []
    min_l,min_r = 10**6,10**6
    for i in range(n):
        t = s[i]
        flag = 0
        l = 0
        r = 0
        for j in range(len(t)):
            if not flag and t[j] == ')':
                r += 1
            elif t[j] == '(':
                flag = 1
                l += 1
            else:
                l -= 1
                if l == 0:
                    flag = 0
        if r == 0 and l == 0:
            continue
        if r == 0:
            L_cnt.append(l)
        elif l == 0:
            R_cnt.append(r)
        else:
            LR_cnt.append([l,r])
            min_l = min(min_l,l)
            min_r = min(min_r,r)
    L,R = sum(L_cnt),sum(R_cnt)
    if not LR_cnt:
        if L == R:
            print('Yes')
            return
        else:
            print('No')
            return
    if not (L_cnt and R_cnt):
        print('No')
        return
    box1 = []
    box2 = []
    for i in range(len(LR_cnt)):
        if L >= LR_cnt[i][1] and LR_cnt[i][1] <= LR_cnt[i][0]:
            L += LR_cnt[i][0] - LR_cnt[i][1]
        elif LR_cnt[i][1] <= LR_cnt[i][0]:
            box1.append(LR_cnt[i])
        else:
            box2.append(LR_cnt[i])
    for i in range(len(box1)):
        L -= box1[i][1]
        if L < 0:
            print('No')
            return
        L += box1[i][0]
    for i in range(len(box2)):
        L -= box2[i][1]
        if L < 0:
            print('No')
            return
        L += box2[i][0]
    if L == R:
        print('Yes')
    else:
        print('No')
    
if __name__ == "__main__":
    main()

Solution (Python):

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for lp in range(N):

    S = input()

    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            dep += 1
        else:
            dep -= 1

        mindep = min(dep,mindep)

    if dep >= 0:
        pl_d.append([mindep,dep])
    else:
        mi_d.append([mindep-dep,-1 * dep])

pl_d.sort()
mi_d.sort()
pl_d.reverse()
mi_d.reverse()



nowp = 0

import sys
for i in range(len(pl_d)):

    nd,np = pl_d[i]

    if nowp + nd < 0:
        print ("No")
        sys.exit()

    nowp += np

nowm = 0

import sys
for i in range(len(mi_d)):

    nd,np = mi_d[i]

    if nowm + nd < 0:
        print ("No")
        sys.exit()

    nowm += np


if nowp != nowm:
    print ("No")
else:
    print ("Yes")

Solution (Python):
import sys


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

A = [[], [], []]

u = 0

for i in range(n):
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            a += 1
        else:
            a -= 1
            b = min(b, a)
    u += a
    if a > 0:
        A[0].append([b, a])
    elif a == 0:
        A[1].append([b, a])
    else:
        A[2].append([a-b, a])



if u != 0:
    print("No")
    sys.exit()



A[0].sort(reverse=True)
A[2].sort()




ng = 0
a = 0
for i in range(len(A[0])):
    a += A[0][i][0]
    if a < 0:
        ng = 1
        break
    a += A[0][i][1]-A[0][i][0]
    if a < 0:
        ng = 1
        break

if ng == 0:
    for i in range(len(A[1])):
        a += A[1][i][0]
        if a < 0:
            ng = 1
            break
        a -= A[1][i][0]

if ng == 0:
    a = 0
    for i in range(len(A[2])):
        aa = A[2][i][1]
        bb = aa-A[2][i][0]
        a -= A[2][i][0]
        if a < 0:
            ng = 1
            break
        a += -bb
        if a < 0:
            ng = 1
            break



if ng == 1:
    print("No")
else:
    print("Yes")

Solution (Python):
import sys
read = sys.stdin.read

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

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')
        exit()
    num += left

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

Solution (Python):
n = int(input())
s = [0] * n
inc = [[] for _ in range(1100000)]
zeros = []
dec = [[] for _ in range(1100000)]

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(i)
    elif start < end:
        inc[minimum].append(i)
    else:
        minimum = minimum - end
        dec[minimum].append(i)

now = 0
for m in range(0, -1000000, -1):
    for i in inc[m]:
        for c in s[i]:
            if c == '(':now += 1
            else: now -= 1
            if now < 0:
                print("No")
                exit()
        
for i in zeros:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()
            
for m in range(-1000000, 1):
    for  i in dec[m]:
        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")

Solution (Python):
import sys
import heapq as hq

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n = ni()
l = [ns() for _ in range(n)]
gu = list()
gd = list()
c = 0
lm = None
for i in range(n):
    s = l[i]
    t = 0
    m = 0
    for x in s:
        if x == '(':
            t += 1
        else:
            t -= 1
            if m > t:
                m = t
    c += t
    if t > 0:
        gu.append((m, t))
    else:
      if t == m and (lm is None or m < lm):
        t = lm
        m, lm = lm, m
      if m is not None:
        gd.append((m, -t))
if c != 0 or lm is None:
    print('No')
    exit(0)
gu.sort(reverse=True)
gd.sort()
cur = 0
q = list()
for m, t in gu:
    if cur + m < 0:
        print('No')
        exit(0)
    cur += t
for m, t in gd:
    if cur + m < 0:
        print('No')
        exit(0)
    cur -= t

print('Yes')

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

N = int(readline())
S = [readline().strip() for i in range(N)]

D = []
L, R = [], []
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')

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

N=int(input())
S=[input().strip() for i in range(N)]

PLUS=[]
MINUS=[]
ZERO=[0]
for br in S:
    NOW=0
    MIN=0
    for b in br:
        if b=="(":
            NOW+=1
        else:
            NOW-=1
            MIN=min(MIN,NOW)

    if NOW>0:
        PLUS.append((NOW,MIN))
    elif NOW<0:
        br2=br[::-1]

        NOW=0
        MIN=0
        for b in br2:
            if b==")":
                NOW+=1
            else:
                NOW-=1
                MIN=min(MIN,NOW)
        MINUS.append((NOW,MIN))
        
    else:
        ZERO.append(MIN)


from operator import itemgetter
PLUS.sort(key=itemgetter(1),reverse=True)

NOW0=0
for p,m in PLUS:
    if NOW0>=-m:
        NOW0+=p
    else:
        print("No")
        sys.exit()

MINUS.sort(key=itemgetter(1),reverse=True)

NOW1=0
for p,m in MINUS:
    if NOW1>=-m:
        NOW1+=p
    else:
        print("No")
        sys.exit()

if NOW0==NOW1 and NOW0>=-min(ZERO):
    print("Yes")
else:
    print("No")

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def f(S):
    worst = 0
    res = 0
    for s in S:
        if(s=='('):
            res += 1
        else:
            res -= 1
        worst = min(worst, res)
    return worst, res
def main():
    N=I()
    S=[ST() for _ in range(N)]
    
    AB_nega=[]
    AB_nonnega=[]
    for i in range(N):
        a,b = f(S[i])
        if b<0:
            AB_nega.append((a,b))
        else:
            AB_nonnega.append((a,b))
    
    AB_nega.sort(key=lambda x:-x[0]+x[1], reverse =True)
    AB_nonnega.sort(reverse = True)

    
    

    now = 0
    for a,b in AB_nonnega:
        if(now+a < 0):
            print("No")
            return
        now += b
        
    
    
    for a,b in AB_nega:
        if(now+a<0):
            print("No")
            return
        now += b
        
    if now == 0:
        print('Yes')
    else:
        print("No")


    
if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
dec_special = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    elif minima < fin:
        dec_special.append((minima, fin))
    else:
        decreasing.append((minima, fin))

increasing.sort(reverse=True)
decreasing.sort()
dec_special.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in dec_special:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
def I():
    s = input()
    mi = 0
    su = 0
    t = 0
    for a in s:
        if a == "(":
            t += 1
        else:
            t -= 1
            mi = min(mi, t)
    return (mi, t)

X = [I() for _ in range(N)]
if sum([x[1] for x in X]):
    print("No")
    exit()

X = sorted(X, key = lambda x: -10**10 if x[0] == 0 else -10**9 - x[0] if x[1] > 0 else x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

Solution (Python):
n=int(input())
sl=0
sr=0
sz=0
lr=[]
rl=[]
for i in range(n):
    s=input()
    l=0
    r=0
    z=0
    for j in s:
        if j=="(":
            l+=1
        else:
            r+=1
        z=max(z,r-l)
    sl+=l
    sr+=r
    if z==0 and l>=r:
        sz+=l-r
    elif l>=r:
        lr.append((z,l-r))
    else:
        rl.append((z,l-r))
if sl!=sr:
    print("No")
    quit()
lr.sort()
for z,i in lr:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
rl.sort(key=lambda x:x[0]+x[1] ,reverse=True)
for z,i in rl:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
print("Yes")

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

MAX = 10**6
N = int(input())
Ss = [input().rstrip() for _ in range(N)]

def calc(S):
    stack = []
    for s in S:
        if s == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            stack.append(s)
    le = 0
    ri = 0
    for s in stack:
        if s == ")":
            le += 1
        else:
            ri += 1
    return le, ri

Ps = [[] for _ in range(MAX+1)]
Qs = [[] for _ in range(MAX+1)]
for S in Ss:
    le, ri = calc(S)
    if ri >= le:
        Ps[le].append(ri-le)
    else:
        Qs[ri].append(le-ri)

T = 0
ok = True
for le, P in enumerate(Ps):
    if P and T < le:
        ok = False
        break
    else:
        T += sum(P)

U = 0
for ri, Q in enumerate(Qs):
    if Q and U < ri:
        ok = False
        break
    else:
        U += sum(Q)

if T != U:
    ok = False
print("Yes" if ok else "No")

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
def I():
    s = input()
    mi = 0
    su = 0
    t = 0
    for a in s:
        if a == "(":
            t += 1
        else:
            t -= 1
            mi = min(mi, t)
    return (mi, t)

X = [I() for _ in range(N)]
if sum([x[1] for x in X]):
    print("No")
    exit()

X = sorted(X, key = lambda x: -10**10 if x[0] == 0 else -10**9 - x[0] if x[1] > 0 else x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
br = [input().rstrip() for i in range(n)]
ls = []
numsum = 0
charge = 0
for i in range(n):
  s = br[i]
  need = 0
  num = 0
  for t in s:
    if t == "(":
      num += 1
    else:
      num -= 1
    need = max(need,-num)
  numsum += num
  if need == 0:
    charge += num
  else:
    ls.append([need,num])
if numsum != 0:
  print("No")
  exit()
ls.sort()
l = len(ls)
vis = [0]*l
for i,x in enumerate(ls):
  need,num = x
  if need <= charge and num >= 0:
    charge += num
    ls[i][0] = -1
ls.sort(key = lambda x:x[0]+x[1],reverse=True)
for i in range(l):
  need,num = ls[i]
  if need == -1:
    continue
  if need > charge:
    print("No")
    exit()
  charge += num
print("Yes")

Solution (Python):
import sys
N = int(input())
dif = [0] * N
mini = [0] * N
for _ in range(N):
    S = input()
    m = 0
    now = 0
    for i in range(len(S)):
        if S[i] == '(':
            now += 1
        else:
            now -= 1
        m = min(m, now)
    dif[_] = now
    mini[_] = m

sum = 0
for i in range(N):
    sum += dif[i]
if sum != 0:
    print('No')
    sys.exit()

plus = []
minus = []
for i in range(N):
    if dif[i] >= 0:
        plus.append((mini[i], dif[i]))
    else:
        minus.append((dif[i] - mini[i], mini[i], dif[i]))
plus.sort(reverse=True)
minus.sort(reverse=True)


now = 0
for i in range(len(plus)):
    if now + plus[i][0] < 0:
        print('No')
        sys.exit()
    now += plus[i][1]

for i in range(len(minus)):
    if now + minus[i][1] < 0:
        print('No')
        sys.exit()
    now += minus[i][2]
print('Yes')

Solution (Python):
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0)
n = int(input())

plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1]
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')':
            cnt += 1
            M = max(M,cnt)
        else:
            cnt -= 1
            
    cnt = 0
    for t in s[::-1]:
        if t == ')':
            cnt += 1
            
        else:
            cnt -= 1
            m = min(m,cnt)
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XY_pos = []
    XY_neg = []
    balance = 0
    for _ in range(N):
        S = input().rstrip('\n')
        st = []
        for s in S:
            if s == "(":
                st.append(s)
            else:
                if st:
                    if st[-1] == "(":
                        st.pop()
                    else:
                        st.append(s)
                else:
                    st.append(s)
        x = y = 0
        for s in st:
            if s == "(":
                y += 1
            else:
                x += 1
        balance += x - y
        if x > y:
            XY_neg.append((x, y))
        else:
            XY_pos.append((x, y))
    if balance:
        print("No")
        exit()

    XY_pos.sort(key=lambda p: p[0])
    val = 0
    for x, y in XY_pos:
        if x > val:
            print("No")
            
            exit()
        val += y - x
    XY_neg.sort(key=lambda p: p[1], reverse=True)
    for x, y in XY_neg:
        if x > val:
            print("No")
            
            exit()
        val += y - x
    print("Yes")


if __name__ == '__main__':
    main()