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

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


sei=[]
hu=[]

for i in range(n):
    l,r=0,0
    for j in range(len(s[i])):
        if s[i][j]==")":
            if r==0:
                l+=1
            else:
                r-=1
        if s[i][j]=="(":
            r+=1
    if r-l>0:
        sei.append([l,r-l])
    else:
        hu.append([r,l-r])

sei.sort(key=lambda x: x[0])
hu.sort(key=lambda x: x[0])

tmp=0

for i in range(len(sei)):
    if tmp-sei[i][0]<0:
        print("No")
        quit()
    tmp+=sei[i][1]

tmp2=0
for i in range(len(hu)):
    if tmp2-hu[i][0]<0:
        print("No")
        quit()
    tmp2+=hu[i][1]

if tmp==tmp2:
    print("Yes")
else:
    print("No")

Solution (Python):
from itertools import accumulate
from bisect import bisect_left
import sys
readlines = sys.stdin.buffer.readlines
readline = sys.stdin.buffer.readline

N = int(readline())

memo = [None]*N

for i,s in enumerate(readlines()):
    s = s.rstrip().decode()
    memo[i] = (min(0,min(accumulate(1 if c =='(' else -1 for c in s))),sum(1 if c =='(' else -1 for c in s))



positives = sorted((m,d) for m,d in memo if d >= 0)
negatives = sorted((m-d,-d) for m,d in memo if d < 0)

def solve():
    left = 0
    for m,d in reversed(positives):
        if left+m < 0:
            return False
        left += d
    right = 0
    for m,d in reversed(negatives):
        if right+m < 0:
            return False
        right += d
    return left == right

print('Yes' if solve() else 'No')

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

N = int(input())
S = [input()[:-1] for _ in range(N)]
high = []
low = []
for i in range(N):
    cnt = 0
    m = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            cnt += 1
        else:
            cnt -= 1
        m = min(m, cnt)
    if cnt > 0:
        high.append([m, cnt])
    else:
        low.append([m-cnt, -cnt])
high.sort(reverse=True)
low.sort(reverse=True)

h = 0
for m, up in high:
    if h+m < 0:
        print("No")
        sys.exit()
    h += up
p = 0
for m, down in low:
    if p+m < 0:
        print("No")
        sys.exit()
    p += down
if h == p:
    print("Yes")
else:
    print("No")

Solution (Python):
def main():
    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:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = -m
        temp[1] = (s.count("(")-s.count(")"))-m
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
cnt=[]
for i in range(n):
	s=input().rstrip()
	l=s.count("(")
	r=s.count(")")
	minus=0
	now=0
	for j in range(len(s)):
		if s[j]=="(":
			now+=1
		else:
			now-=1
			minus=min(minus,now)
	cnt.append((l,r,s,minus))
cnt.sort(key=lambda x:x[1]-x[0])
plus=[]
minus=[]

for x in cnt:
	if x[0]-x[1]>0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])
minus.sort(key=lambda x:-(x[0]-x[1]-x[3]))
lr=0
for x in plus+minus:
	if lr+x[3]<0:
		print("No")
		exit()
	lr+=x[0]-x[1]
if lr==0:
	print("Yes")
else:
	print("No")

Solution (Python):
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    L1 = []
    L2 = []
    for i in range(N):
        t = 0
        mint = 0
        for s in S[i]:
            if s == "(":
                t += 1
            else:
                t -= 1
            mint = min(mint, t)
        if t >= 0:
            L1.append((t, mint))
        else:
            t = 0
            mint = 0
            for j in range(len(S[i]) - 1, -1, -1):
                if S[i][j] == ")":
                    t += 1
                else:
                    t -= 1
                mint = min(mint, t)
            L2.append((t, mint))

    L1.sort(key=lambda x: x[1], reverse=True)
    L2.sort(key=lambda x: x[1], reverse=True)
    t1 = 0
    for l, m in L1:
        if t1 + m < 0:
            return False
        t1 += l
    t2 = 0
    for l, m in L2:
        if t2 + m < 0:
            return False
        t2 += l
    if t1 == t2:
        return True
    return False


if main():
    print("Yes")
else:
    print("No")

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    s = SR(n)
    m = []
    x = []
    for si in s:
        l = 0 
        r = 0 
        for i in si:
            if i == ")":
                if r:
                    r -= 1
                else:
                    l += 1
            elif i == "(":
                r += 1
        if r > l:
            m.append((l, r))
        else:
            x.append((r, l))
    m.sort()
    x.sort(reverse=True)
    tmp = 0
    for l, r in m:
        if tmp - l < 0:
            print("No")
            return
        else:
            tmp -= l
            tmp += r
    for r, l in x:
        if tmp - l < 0:
            print("No")
            return
        else:
            tmp -= l
            tmp += r
    if tmp == 0:
        print("Yes")
    else:
        print("No")
    return



if __name__ == '__main__':
    solve()

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

def count(s):
    m=0
    e=0
    for t in s:
        if t=='(':
            e+=1
        else:
            e-=1
            m=min(m,e)
    return (e,m)
def count_reverse(s):
    m=0
    e=0
    for t in s[::-1]:
        if t==')':
            e+=1
        else:
            e-=1
            m=min(m,e)
    return (e,m)

def main():
    n=int(input())
    S=[input().strip() for _ in range(n)]
    P,M=[],[]
    Z=[0]
    for s in S:
        e,m=count(s)
        if e>0:
            P.append((m,e))
        elif e<0:
            e,m=count_reverse(s)
            M.append((m,e))
        else:
            Z.append(m)
    P.sort(reverse=True); M.sort(reverse=True)
    s_p,s_m=0,0
    for m,e in P:
        if s_p+m<0:
            return 'No'
        s_p+=e
    for m,e in M:
        if s_m+m<0:
            return 'No'
        s_m+=e
    if s_p==s_m and s_p+min(Z)>=0:
        return 'Yes'
    return 'No'

if __name__=='__main__':
    print(main())

Solution (Python):
n=int(input())
lipp = []
lipm = []
limm = []
allcnt = 0
for _ in range(n):
    s = input()
    cnt = 0
    mi = 0
    for x in s:
        cnt += 1 if x == '(' else -1
        mi = min(mi,cnt)

    if cnt >= 0:
        lipm.append([mi,cnt])
    else:
        limm.append([mi - cnt, -cnt])
    allcnt += cnt
if allcnt != 0:
    print('No')
    exit()

lipm.sort(reverse = True)
limm.sort(reverse = True)

def solve(l):
    now = 0
    for mi, cnt in l:
        if mi + now < 0:
            print('No')
            exit()
        now += cnt

solve(lipm)
solve(limm)

print("Yes")

Solution (Python):
def main():

    N = int(input())
    S = []
    pos = []
    neg1 = []
    neg2 = []
    tot_v = 0
    for _ in range(N):
        t = input()
        S.append(t)
        v = 0
        min_v = float('inf')
        for c in t:
            if c == '(': v += 1
            else: v -= 1
            min_v = min(min_v, v)
        tot_v += v
        if min_v >=0:
            pos.append([min_v, v])
        else:
            if v > 0:
                neg1.append([min_v, v])
            else:
                neg2.append([min_v-v, min_v, v])

    if tot_v !=  0: return "No"

    u = 0
    for _, v in pos:
        u += v

    neg1.sort(reverse = True, key = lambda x: x[0])
    for min_v, v in neg1:
        if u + min_v < 0:
            return "No"
        else:
            u += v


    neg2.sort(key = lambda x: x[0])
    for _, min_v, v in neg2:
        if u + min_v < 0:
            return "No"
        else:
            u += v

    return "Yes"


if __name__ == '__main__':
    print(main())

Solution (Python):
(N,) = [int(x) for x in input().split()]
brackets = [input() for i in range(N)]

delta = []
minDelta = []
for s in brackets:
    balance = 0
    mn = 0
    for c in s:
        if c == "(":
            balance += 1
        else:
            balance -= 1
        mn = min(mn, balance)
    delta.append(balance)
    minDelta.append(mn)

if sum(delta) == 0:
    
    
    
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: minDelta[i], reverse=True)

    
    eqIndices = [i for i in range(N) if delta[i] == 0]

    
    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: delta[i] - minDelta[i], reverse=True)

    balance = 0
    for i in posIndices + eqIndices + negIndices:
        if balance + minDelta[i] < 0 or balance + delta[i] < 0:
            print("No")
            exit()
        balance += delta[i]
    assert balance == 0

    print("Yes")
else:
    print("No")

Solution (Python):

import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

YES = "Yes"  
NO = "No"  


def solve(N: int, S: "List[str]"):
    s_plus = []
    s_minus = []
    total = 0
    last = 0
    for s in S:
        l = 0
        r = 0
        for v in s:
            if v == '(':
                l += 1
            elif v == ')':
                if l > 0:
                    l = l - 1
                else:
                    r += 1
        
        
        
        
        if l >= r:
            s_plus.append([l, r])
        else:
            s_minus.append([l, r])

    s_plus.sort(key=lambda x: x[1])
    s_minus.sort(key=lambda x: -x[0])
    
    total = 0
    for l, r in s_plus + s_minus:
        total -= r
        if total < 0:
            print(NO)
            return
        total += l
    if total == 0:
        print(YES)
    else:
        print(NO)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = [next(tokens) for _ in range(N)]  
    solve(N, S)


if __name__ == '__main__':
    main()

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

def calc(T):
    now = 0
    ret = 0
    for s in T:
        if s == '(':
            now += 1
        elif s == ')':
            now -= 1
        ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    less = -calc(s)
    if less == 0:
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append((less, s))
        else:
            L.append((less - (r - l), s))

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]
ans = ''.join(H) + ''.join(P) + ''.join(L)

l = ans.count('(')
r = len(ans) - l

if l != r or calc(ans) < 0:
    print('No')
else:
    print('Yes')

Solution (Python):
(N,) = [int(x) for x in input().split()]
brackets = [input() for i in range(N)]

delta = []
minDelta = []
for s in brackets:
    balance = 0
    mn = 0
    for c in s:
        if c == "(":
            balance += 1
        else:
            balance -= 1
        mn = min(mn, balance)
    delta.append(balance)
    minDelta.append(mn)

if sum(delta) == 0:
    
    
    
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: (minDelta[i], delta[i]), reverse=True)

    
    eqIndices = [i for i in range(N) if delta[i] == 0]

    
    negIndices = [i for i in range(N) if delta[i] < 0]
    negIndices.sort(key=lambda i: (delta[i] - minDelta[i], minDelta), reverse=True)

    balance = 0
    for i in posIndices + eqIndices + negIndices:
        if balance + minDelta[i] < 0 or balance + delta[i] < 0:
            print("No")
            exit()
        balance += delta[i]
    assert balance == 0

    print("Yes")
else:
    print("No")

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

N = int(input())
op = []
ed = []
mid = [0]
dg = 10**7

for _ in range(N):
    s = list(input())
    n = len(s)-1

    a,b,st = 0,0,0
    for e in s:
        if e == '(':
            st += 1
        elif e == ')':
            if st > 0:
                st -= 1
            else:
                a += 1
    st = 0
    for i in range(n-1,-1,-1):
        if s[i] == ')':
            st += 1
        else:
            if st > 0:
                st -= 1
            else:
                b += 1
    if a > b:
        ed.append(b*dg + a)
    elif a == b:
        mid.append(a)
    else:
        op.append(a*dg + b)

op.sort()
ed.sort()

p = 0
for e in op:
    a,b = divmod(e,dg)
    if p < a:
        print('No')
        exit()
    p += b-a

q = 0
for e in ed:
    b,a = divmod(e,dg)
    if q < b:
        print('No')
        exit()
    q += a-b

if p == q and p >= max(mid):
    print('Yes')
else:
    print('No')

Solution (Python):

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (-r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")

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

def solve():
    N = int(input())
    Sss = [input().rstrip() for _ in range(N)]

    numL = numR = 0
    Pluss, Evens, Minuss = [], [], []
    for Ss in Sss:
        nums = [0] + [1 if S == '(' else -1 for S in Ss]
        nums = list(accumulate(nums))
        x = min(nums)
        y = nums[-1] - x
        x, y = abs(x), abs(y)
        if x == 0:
            numL += y
        elif y == 0:
            numR += x
        else:
            if x > y:
                Minuss.append((x, y))
            elif x < y:
                Pluss.append((x, y))
            else:
                Evens.append((x, y))

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

    v = numL
    for x, y in Pluss:
        v -= x
        if v < 0:
            return False
        v += y
    for x, y in Evens:
        v -= x
        if v < 0:
            return False
        v += y
    for x, y in Minuss:
        v -= x
        if v < 0:
            return False
        v += y
    v -= numR
    return v == 0


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

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
cnt=[]
for i in range(n):
	s=input().rstrip()
	l=s.count("(")
	r=s.count(")")
	minus=0
	now=0
	for j in range(len(s)):
		if s[j]=="(":
			now+=1
		else:
			now-=1
			minus=min(minus,now)
	cnt.append((l,r,s,minus))
cnt.sort(key=lambda x:x[1]-x[0])
plus=[]
minus=[]
first=[]
for x in cnt:
	if x[3]>=0:
		first.append(x)
	elif x[0]-x[1]>0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])
minus.sort(key=lambda x:-(x[0]-x[1]-x[3]))
l=r=0
for x in first+plus+minus:
	for i in range(len(x[2])):
		if x[2][i]=="(":
			l+=1
		else:
			r+=1
		if l<r:
			print("No")
			exit()
if l==r:
	print("Yes")
else:
	print("No")

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)
from heapq import heappush, heappop

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


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

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

left = 0
right = 0

l_ok = [False] * n
r_ok = [False] * n
lmr = [0] * n
min_lmr = [INF] * n

for i,s in enumerate(S):
    l = 0
    r = 0
    lok = True
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                lok = False
            min_lmr[i] = min(min_lmr[i], l-r)
    lmr[i] = l - r
    l = 0
    r = 0
    rok = True
    for j in range(len(s)-1, -1, -1):
        if s[j] == "(":
            l += 1
            if l > r:
                rok = False
                break
        else:
            r += 1

    left += s.count("(")
    right += s.count(")")

    l_ok[i] = lok
    r_ok[i] = rok




if left != right:
    print("No")
    exit()

strs = []


for i in range(n):
    if l_ok[i]:
        strs.append(S[i])


ngs = []
for i in range(n):
    if not l_ok[i] and not r_ok[i]:
        
        ngs.append((-1 * (min_lmr[i] + lmr[i]), i))

ngs.sort()

for ng in ngs:
    strs.append(S[ng[1]])


for i in range(n):
    if r_ok[i] and not l_ok[i]:
        strs.append(S[i])





l = 0
r = 0
for s in strs:
    for j,c in enumerate(s):
        if c == "(":
            l += 1
        else:
            r += 1
            if r > l:
                print("No")
                exit()
print("Yes")

Solution (Python):




def main():
  values = []
  total = 0
  open_chars = 0
  close_chars = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    if open_required == 0 and close_required == 0 and open_close == 0:
      continue
    elif open_close == len(s):
      open_chars += len(s)
      continue
    elif -open_close == len(s):
      close_chars += len(s)
      continue

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total + open_chars - close_chars != 0:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f + open_chars:
      print('No')
      return

    if creq_b > open_close_b + close_chars:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Solution (Python):
n,inc,dec=int(input()),[],[]
for _ in range(n):
  s,d,r=input(),0,0
  for c in s:
    d=d+(1 if c=='(' 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,p2,ok=0,0,True
for s in inc:
  ok&=s[1]<=p1
  p1+=s[0]
for s in dec:
  ok&=p2>=s[0]+s[1]
  p2-=s[0]
ok&=p1==p2
print('Yes'if ok else'No')

Solution (Python):
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-(r-m), -r, m))
        else:
            pos += r
 
    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for _, r, m in negn:
        if pos + m < 0:
            return False
        pos -= r
    return pos == 0
 
print('Yes' if main() else 'No')

Solution (Python):
N = int(input())
S = list(input() for _ in range(N))
X = []
for s in S:
    l,r = 0,0
    for c in s:
        if c == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
        else:
            r += 1
    X.append([l,r])
X.sort(key = lambda x:x[0])
Y = []
L = 0
for p,q in X:
    if p > L:
        print("No")
        quit()
    if q >= p:
        L -= p
        L += q
    else:
        Y.append([p,q])
Y.sort(key = lambda x:-x[1])
for a,b in Y:
    if a > L:
        print("No")
        quit()
    L -= a
    L += b
if L:
    print("No")
else:
    print("Yes")

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():  
    N = int(input())
    flag1 = False
    flag2 = False
    left = 0
    left2 = []
    right = 0
    right2 = []
    for _ in range(N):
        s = input()
        stack = ['-']
        for t in s:
            if t == '(':
                stack.append(t)
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
        if len(stack) == 1:
            continue
        elif stack[1] == '(':
            flag1 = True
            left += len(stack) - 1
        elif len(stack) >= 3  and stack[1] == ')' and stack[-1] == '(':
            for i in range(len(stack)):
                if stack[i] == '(':
                    s = i
                    break
            left2.append(len(stack) - s)
            right2.append(s - 1)
        else:
            flag2 = True
            right += len(stack) - 1
    if (right == 0 and left == 0 and  sum(right2) == 0 and sum(left2) == 0):
        print('Yes')
    else:
        l = 0
        if len(left2) > 0:
            l = min(left2)
        r = 0
        if len(right2) > 0:
            r = min(right2)
        x = max(r,l)
        if flag1 and flag2 and (right + sum(right2) == left + sum(left2)) and (left >= x) and (right >= x):
            print('Yes')
        else:
            print('No')
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = []
for i in range(n):
    temp = input()
    count = 0
    min_count = 0
    for j in temp:
        if j == "(":
            count += 1
        else:
            count -= 1
            min_count = min(min_count, count)
    s.append([count, min_count])
sum_count = sum([s[i][0] for i in range(n)])
if sum_count != 0:
    print("No")
else:
    s2 = [s[i] for i in range(n) if s[i][0] >= 0]
    s3 = [s[i] for i in range(n) if s[i][0] < 0]
    s2.sort(key = lambda x: x[1], reverse = True)
    s3.sort(key = lambda x: x[1] - x[0])
    flag = True
    count = 0
    for i in range(len(s2)):
        if count + s2[i][1] < 0:
            flag = False
            break
        else:
            count += s2[i][0]
    for i in range(len(s3)):
        if count + s3[i][1] < 0:
            flag = False
            break
        else:
            count += s3[i][0]
    if flag == True:
        print("Yes")
    else:
        print("No")

Solution (Python):




def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  if len(values) > 500000:
    print('Yes')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Solution (Python):
N=int(input())
S=[]
L=0
R=0
for i in range(N):
    s=input()
    n=len(s)
    data=[s[j] for j in range(n)]
    l=0
    r=0
    yabai=float("inf")
    for j in range(n):
        l+=(s[j]=="(")
        r+=(s[j]==")")
        yabai=min(l-r,yabai)
    S.append([yabai,l-r])
    L+=l
    R+=r

if L!=R:
    print("No")
else:
    first=[]
    last=[]
    for i in range(N):
        yabai,gap=S[i]
        if gap>0:
            first.append(S[i])
        else:
            last.append([gap-yabai,yabai])
    first.sort(reverse=True)
    last.sort(reverse=True)
    G=0
    for i in range(len(first)):
        yabai,gap=first[i]
        if 0>G+yabai:
            print("No")
            exit()
        else:
            G+=gap
    for j in range(len(last)):
        gapminus,yabai=last[j]
        if 0>G+yabai:
            print("No")
            break
        else:
            G+=gapminus+yabai
    else:
        print("Yes")

Solution (Python):
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-(r-m), -r, m))
        else:
            pos += r

    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for _, r, m in negn:
        if pos + m < 0:
            return False
        pos -= r
    return pos == 0

print('Yes' if main() else 'No')

Solution (Python):
import sys
def input():
    return sys.stdin.readline().strip()

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

'''
N = sum([len(i) for i in s])
R = sum([i.count('(') for i in s])
if N % 2 == 1 or s.count('(') != N // 2:
    print('No')
    exit()
'''

bothleft = []
bothright = []
bothneutral = [0]
left = [0]
right = [0]

for i in s:
    lnum = 0
    now = 0
    for j in range(len(i)):
        if i[j] == '(':
            now -= 1
        else:
            now += 1
            lnum = max([lnum, now])

    rnum = 0
    now = 0
    for j in range(len(i) - 1, -1, -1):
        if i[j] == ')':
            now -= 1
        else:
            now += 1
            rnum = max([rnum, now])
    
    if lnum > 0:
        if rnum > 0:
            if lnum > rnum:
                bothleft.append((rnum, lnum - rnum))
            elif rnum > lnum:
                bothright.append((lnum, rnum - lnum))
            else:
                bothneutral.append(lnum)
        else:
            left.append(lnum)
    elif rnum > 0:
        right.append(rnum)

bothneutral = max(bothneutral)
bothleft.sort()
bothright.sort()

lsum = sum(left)
for i in range(len(bothleft)):
    if bothleft[i][0] > lsum:
        print('No')
        exit()
    lsum += bothleft[i][1]

if bothneutral > lsum:
    print('No')
    exit()

rsum = sum(right)
for i in range(len(bothright)):
    if bothright[i][0] > rsum:
        print('No')
        exit()
    rsum += bothright[i][1]

if lsum != rsum:
    print('No')
    exit()

print('Yes')