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:
from itertools import permutations
n = int(input())
s = [input() for i in range(n)]
lsa=list() #mn,end
lsd=list()
for i in range(n):
    now = 0
    mn = 0
    for c in s[i]:
        if c == '(':
            now += 1
        else:
            now -= 1
            mn = min(mn,now)
    if now >= 0:
        lsa.append([mn,now])
    else:
        lsd.append([mn-now,-now])

lsa.sort(reverse=True)
tmn = 0
tend = 0
flag=True
# ascent
for mn,end in lsa:
    tmn = mn + tend
    tend += end
    if tmn < 0 or tend < 0:
        flag = False
        break
tenda = tend

# descent
lsd.sort(reverse=True)
tmn = 0
tend = 0

for mn,end in lsd:
    tmn = mn + tend
    tend += end
    if tmn < 0 or tend < 0:
        flag=False
        break

if flag and tend == tenda:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 998244353


def main():

    """
    各トークンを(最下点、最終的な高さ)に分けるのはできた。
    そしてそれらを最下点位置が浅い順に並べるのも悪くはなかった、増加パートに関しては。

    減少パートは減少度合が小さい順に付け加えたとしても高さが負に潜り込むケースがある。
    （例）高さ3から下るとして、(-1, -1), (-2, 0), (-3, -2)が各トークンとすると
        この順にくっつけると(-3, -2)を加えるときにアウトだが、
        (-2, 0), (-3, -2), (-1, -1)の順だったらOK
    
    なので下る場合には増加パートとは違う方法でくっつけないといけない。
    結論としては、これは左右反転させれば増加していることになるので、右からくっつけるようにすればいい。
    """

    N = int(input())
    S_up = []
    S_down = []
    for _ in range(N):
        s = input()
        max_depth = 0
        height = 0
        for c in s:
            if c == '(':
                height += 1
            else:
                height -= 1
                max_depth = min(max_depth, height)
        if height > 0: S_up.append((max_depth, height - max_depth))
        else: S_down.append((-(height - max_depth), -max_depth))
    S_up.sort(key=lambda x: (x[0], x[1]))
    S_down.sort(key=lambda x: (x[0], x[1]))

    height_left = 0
    while S_up:
        d, h = S_up.pop()
        #print("({}, {})".format(d, h))
        if height_left + d < 0:
            print("No")
            return
        height_left += d+h

    height_right = 0
    while S_down:
        d, h = S_down.pop()
        #print("({}, {})".format(d, h))
        if height_right + d < 0:
            print("No")
            return
        height_right += d+h

    if height_left != height_right: print("No")
    else: print("Yes")





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
S = [input() for _ in range(N)]

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l1 = []
l2 = []
m1 = 0
m2 = 0
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2==0:
        continue
    if n1 == 0:
        m1 += n2
        continue
    if n2 == 0:
        m2 += n1
        continue
    if n2-n1>=0:
        l1.append([n1,n2])
    else:
        l2.append([n1,n2])

ans = 'Yes'
l1.sort()
for i in range(len(l1)):
    n1,n2 = l1[i]
    if m1 < n1:
        ans = 'No'
        break
    m1 += n2-n1

l2.sort(key=lambda x:x[1])
for i in range(len(l2)):
    n1,n2 = l2[i]
    if m2 < n2:
        ans = 'No'
        break
    m2 += n1-n2

if m1!=m2:
    ans = 'No'

print(ans)

Submission status: Accepted

Solution code:
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)]
# lst=[[0]*2 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")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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=[]
#x[3]は最小値　x[0]-x[1]が合計値
for x in cnt:
	if x[0]-x[1]>0:
		plus.append(x)
	else:
		minus.append(x)
plus.sort(key=lambda x:-x[3])#最小値の少ない(0に近い方から)
minus.sort(key=lambda x:-(x[0]-x[1]-x[3]))
lr=0#l-r
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")

Submission status: Accepted

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

Submission status: Accepted

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

#solve
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


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
(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:
    # Want to get balance as high as possible
    # Take any positive as long there's enough balance to absorb their minDelta
    # Can sort since anything that works will only increase balance and the ones with worse minDelta comes later
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: minDelta[i], reverse=True)

    # At the top can take all with zero delta, just need to absorb minDelta
    eqIndices = [i for i in range(N) if delta[i] == 0]

    # When going back down, want to preserve existing balance as much as possible but take a hit for stuff that does need to use the balance to absorb minDelta
    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")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

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

YES = "Yes"  # type: str
NO = "No"  # type: str


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 r == 0:
        #     total += l
        # elif l ==0:
        #     last += r
        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])
    # print(s_plus, s_minus)
    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))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
(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:
    # Want to get balance as high as possible
    # Take any positive delta first as long there's enough balance to absorb their minDelta
    # Can sort since any that works will only increase balance and the ones with worse minDelta comes last
    posIndices = [i for i in range(N) if delta[i] > 0]
    posIndices.sort(key=lambda i: (minDelta[i], delta[i]), reverse=True)

    # At the top can take all with zero delta, just need to absorb minDelta
    eqIndices = [i for i in range(N) if delta[i] == 0]

    # When going back down, 
    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")

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# 改行区切りの入力をn行読み込んで数値リストにして返します。
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

# log(l_ok)
# log(r_ok)

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

strs = []

# LeftOKを並べる
for i in range(n):
    if l_ok[i]:
        strs.append(S[i])

# LeftもRightもだめなやつをminL-Rが多い順に並べる
ngs = []
for i in range(n):
    if not l_ok[i] and not r_ok[i]:
        # ngs.append((-1 * min_lmr[i], -1 * lmr[i], i))
        ngs.append((-1 * (min_lmr[i] + lmr[i]), i))

ngs.sort()

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

# RightOKを並べる
for i in range(n):
    if r_ok[i] and not l_ok[i]:
        strs.append(S[i])

# log(ngs)
# log(min_lmr)
# log("".join(strs))

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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