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: Wrong Answer

Solution code:
N = int(input())
array = []
for i in range(N):
    s = input()
    x1 = 0
    x2 = 0
    x3 = 0
    flag = True
    for i in range(len(s)):
        if s[i] == "(":
            if flag:
                x3 = 1
            else:
                x3 += 1
            flag = False
            x1 += 1
        else:
            x1 -= 1
            if flag:
                x2 += 1
            else:
                x3 -= 1
    if x3 < 0:
        x2 = x2 - x3
    array.append((-x2,x1))
array.sort(reverse = True)
sum = 0
ans = True
for i in range(N):
    if sum + array[i][0] >= 0:
        sum += array[i][1]
    else:
        ans = False

if sum != 0:
    ans = False

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

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for _ in range(n)]
U = []
L = []
for s in S:
  l, r = 0, 0
  for t in s:
    if t == "(":
      r += 1
    else:
      if r > 0:
        r -= 1
      else:
        l += 1
  if l <= r:
    U.append((l, r-l))
  else:
    L.append((l-r, l))
U.sort()
L.sort()
temp = 0
for a, c in U:
  if temp < a:
    print("No")
    exit()
  temp += c
for c, a in L:
  if temp < a:
    print("No")
    exit()
  temp -= c
if temp != 0:
  print("No")
  exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
S = [input() for _ in range(n)]
U = []
L = []
for s in S:
  l, r = 0, 0
  for t in s:
    if t == "(":
      r += 1
    else:
      if r > 0:
        r -= 1
      else:
        l += 1
  if l <= r:
    U.append((l, r-l))
  else:
    L.append((l, l-r))
U.sort()
L.sort(reverse=True)
temp = 0
for a, c in U:
  if temp < a:
    print("No")
    exit()
  temp += c
for a, c in L:
  if temp < a:
    print("No")
    exit()
  temp -= c
if temp != 0:
  print("No")
  exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())
D = []
t = 0
for _ in range(N):
    S = input().rstrip()
    x,y = 0,0
    for s in S:
        if s=="(": x+=1
        else: x=max(x-1,0)
    for s in reversed(S):
        if s==")": y+=1
        else: y=max(y-1,0)
    if y==0: t += x
    else: D.append((x,y))
D.sort(key=lambda x:x[1]-x[0])
for x,y in D:
    if t-y<0: print("No"); exit()
    else: t += x-y
if t==0: print("Yes"); exit()
else: print("No"); exit()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())

a = []

# 右の余りがゼロ
right0 = []
for _ in range(n):
    s = input()
    b = c = 0

    # sの中でペアにならない括弧を計算
    for t in s:
        if t == '(':
            b += 1
        else:
            if b == 0:
                c += 1
            else:
                b -= 1

    if c == 0:
        right0.append((b, c))
    else:
        a.append((c, b))
now = 0
for x, y in right0:
    now += x

# ここまではおｋ？
# 現状(((((((((((となっている
# )))(みたいなやつ
# )(((みたいなやつどう選ぶか？
a.sort()
ok = True
tmp = now
for x, y in a:
    tmp -= x
    if tmp < 0:
        ok = False
    tmp += y

if ok and tmp == 0:
    print('Yes')
    exit()

a = a[::-1]
ok = True
for x, y in a:
    tmp -= x
    if tmp < 0:
        ok = False
    tmp += y
if ok and tmp == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())

a = []

# 右の余りがゼロ
right0 = []
for _ in range(n):
    s = input()
    b = c = 0

    # sの中でペアにならない括弧を計算
    for t in s:
        if t == '(':
            b += 1
        else:
            if b == 0:
                c += 1
            else:
                b -= 1

    if c == 0:
        right0.append((b, c))
    else:
        a.append((c, b))
a.sort()
now = 0
for x, y in right0:
    now += x

for x, y in a:
    now -= x
    if now < 0:
        print('No')
        exit()
    now += y
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())

a = []

for _ in range(n):
    s = input()
    b = c = 0

    for t in s:
        if t == '(':
            b += 1
        else:
            if b == 0:
                c += 1
            else:
                b -= 1

    a.append((c, b))


a.sort()

now = 0
ok = True
for i in range(n):
    now -= a[i][1]
    if now < 0:
        ok = False
    now += a[i][0]
if ok:
    print('Yes')
    exit()

a = a[::-1]
now = 0
ok = True
for i in range(n):
    now -= a[i][1]
    if now < 0:
        ok = False
    now += a[i][0]


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

Submission status: Wrong Answer

Solution code:
N = int(input())
C = {0:[],1:[],2:[]}
for i in range(N):
    S = input().strip()
    A = []
    for j in range(len(S)):
        if S[j]=="(":
            A.append(S[j])
        else:
            if len(A)>0 and A[-1]=="(":
                A.pop()
            else:
                A.append(S[j])
    if len(A)==0:continue
    if A[0]=="(":
        C[0] += A
    else:
        if A[-1]=="(":
            C[1] += A
        else:
            C[2] += A
x = C[0]+C[1]+C[2]
A = []
flag = 0
for i in range(len(x)):
    a = x[i]
    if a=="(":
        A.append(a)
    else:
        if len(A)==0 or A[-1]==")":
            flag = 1
            break
        else:
            A.pop()
if flag==0 and len(A)==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
C = {0:[],1:[],2:[]}
for i in range(N):
    S = input().strip()
    A = []
    for j in range(len(S)):
        if S[j]=="(":
            A.append(S[j])
        else:
            if len(A)>0 and A[-1]=="(" and S[j]==")":
                A.pop()
            else:
                A.append(S[j])
    if len(A)==0:continue
    if A[0]=="(":
        C[0].append(A)
    else:
        if A[-1]=="(":
            C[1].append(A)
        else:
            C[2].append(A)
x = []
for y in C[0]:
    x += y
for y in C[1]:
    x += y
for y in C[2]:
    x += y
A = []
flag = 0
for i in range(len(x)):
    a = x[i]
    if a=="(":
        A.append(a)
    else:
        if len(A)==0 or A[-1]==")":
            flag = 1
            break
        else:
            A.pop()
if flag==0 and len(A)==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == "(":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = set()
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.add(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.add(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: (x[1], -x[0]))

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")
	
	
#23, 31, 41, 43 wa
#1, 2, 3, 4, tle

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == ".":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = set()
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.add(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.add(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: x[1])

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")
	
	
#23, 31, 41, 43 wa
#1, 2, 3, 4, tle

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == ".":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = set()
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.add(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.add(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: (x[1], -x[0]))

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")
	
	
#23, 31, 41, 43 wa
#1, 2, 3, 4, tle

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == ".":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = []
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.append(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.append(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: (x[1], -x[0]))

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")
	
	
#23, 31, 41, 43 wa
#1, 2, 3, 4, tle

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == ".":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = []
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.append(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.append(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: (x[1], x[1] - x[0]))

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == "(":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = []
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.append(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.append(i)
lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: x[1])

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left-right
        if leftdiff >= 0:
            P.append((leftdiff, rightmax, 0, s))
            continue
            
        left = 0
        right = 0
        leftmax = 0
        for c in reversed(s):
            if c == "(":
                left += 1
            else:
                right += 1
            leftmax = max(leftmax, right - left)
        M.append((leftdiff, 0, leftmax, s))

    R = []
    for e in sorted(P, key=lambda _e: _e[1]):
        R.append(e[3])
    for e in sorted(M, key=lambda _e: _e[2], reverse=True):
        R.append(e[3])

    nleft = 0
    for c in "".join(R):
        if c == "(":
            nleft += 1
        else:
            nleft -= 1
        if nleft < 0:
            print("No")
            return
        
    if nleft == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        leftmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
            leftmax = max(leftmax, left - right)
        leftdiff = left - right
        if leftdiff >= 0:
            P.append((leftdiff, rightmax, leftmax, s))
        else:
            M.append((leftdiff, rightmax, leftmax, s))

    R = []
    for e in sorted(P, key=lambda _e: _e[1]):
        R.append(e[3])
    for e in sorted(M, key=lambda _e: _e[2], reverse=True):
        R.append(e[3])

    nleft = 0
    for c in "".join(R):
        if c == "(":
            nleft += 1
        else:
            nleft -= 1
        if nleft < 0:
            print("No")
            return
        
    if nleft == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right
        rightmax = rightmax
        if leftdiff >= 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    MM = list(sorted(M, key=lambda _e: _e[0], reverse=True))
    used = [False] * len(MM)
    for i in range(len(MM)):
        for j in range(len(MM)):
            if used[j]:
                continue
            e = MM[j]
            if nleft - e[1] >= 0:
                used[j] = True
                nleft += e[0]
                break
        else:
            print("No")
            return

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


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right       
        if leftdiff >= 0:
            P.append((leftdiff, rightmax, s))
        else:
            M.append((leftdiff, rightmax, s))

    R = []
    for e in sorted(P, key=lambda _e: _e[1]):
        R.append(e[2])
    for e in sorted(M, key=lambda _e: _e[1], reverse=True):
        R.append(e[2])

    left = 0    
    for c in "".join(R):
        if c == "(":
            left += 1
        else:
            left -= 1
        if left < 0:
            print("No")
            return
    if left == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right       
        if leftdiff >= 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    for e in sorted(M, key=lambda _e: _e[0], reverse=True):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

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


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        leftmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
            leftmax = max(leftmax, left - right)
        leftdiff = left - right       
        if leftdiff >= 0:
            P.append((leftdiff, rightmax, leftmax))
        else:
            M.append((leftdiff, rightmax, leftmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    for e in sorted(M, key=lambda _e: _e[2], reverse=True):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

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


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right
        rightmax = rightmax
        if leftdiff >= 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    for e in sorted(M, key=lambda _e: _e[1], reverse=True):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

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


main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right
        rightmax = rightmax
        if leftdiff > 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    for e in sorted(M, key=lambda _e: _e[1], reverse=True):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

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


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

    for st in MM:
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

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


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

    MMS = list(sorted(MM, key=lambda _st: _st.leftdiff, reverse=True))
    used = [False] * len(MMS)
    for i in range(len(MMS)):
        for j in range(len(MMS)):
            if used[j]:
                continue
            if MMS[j].rightmax <= nleft:
                used[j] = True
                nleft += MMS[j].leftdiff
                break
        else:
            print("No")
            return
                
    if nleft == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

    MMS = list(sorted(MM, key=lambda _st: _st.leftdiff, reverse=True))
    used = [False] * len(MMS)
    for i in range(len(MMS)):
        for j in range(len(MMS)):
            if used[j]:
                continue
            if MMS[j].rightmax <= nleft:
                used[j] = True
                if nleft - MMS[j].rightmax < 0:
                    print("No")
                    return
                nleft += MMS[j].leftdiff
                break

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


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

    MMS = list(sorted(MM, key=lambda _st: _st.leftdiff, reverse=True))
    used = [False] * len(MMS)
    for i in range(len(MMS)):
        for j in range(len(MMS)):
            if used[j]:
                continue
            if MMS[j].rightmax <= nleft:
                used[j] = True
                if nleft - MMS[j].rightmax < 0:
                    print("No")
                    return
                nleft += MMS[j].leftdiff

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


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff

    MMS = list(sorted(MM, key=lambda _st: _st.leftdiff, reverse=True))
    used = [False] * len(MMS)
    for i in range(len(MMS)):
        for j in range(len(MMS)):
            if used[j]:
                continue
            if MMS[j].rightmax <= nleft:
                used[j] = True
                if nleft - MMS[j].rightmax < 0:
                    print("No")
                    return
                nleft += st.leftdiff

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


main()

Submission status: Wrong Answer

Solution code:
class ST(object):
    s: str
    leftdiff: int
    rightmax: int


def main():
    N = int(input())
    PM = []
    PP = []
    MP = []
    MM = []
    for i in range(N):
        s = input()
        st = ST()
        st.s = s

        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        st.leftdiff = (left - right)
        st.rightmax = rightmax

        if st.leftdiff > 0 and st.rightmax <= 0:
            PM.append(st)
        if st.leftdiff > 0 and st.rightmax > 0:
            PP.append(st)
        if st.leftdiff <= 0:
            MM.append(st)

        # if st.leftdiff <= 0 and st.rightmax <= 0:
        #     MM.append(st)
        # if st.leftdiff <= 0 and st.rightmax > 0:
        #     MP.append(st)

    nleft = 0
    for st in PM:
        nleft += st.leftdiff
    for st in sorted(PP, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff
    for st in sorted(MM, key=lambda _st: _st.rightmax):
        if nleft - st.rightmax < 0:
            print("No")
            return
        nleft += st.leftdiff
    if nleft == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Wrong Answer

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())
L = [input() for _ in range(N)]

up = []
do = []
for li in L:
    l, r = 0, 0
    ext_neg = 0
    ext_pos = 0
    for op in li:
        if op == "(":
            l += 1
        elif op == ")":
            r += 1
        ext_neg = min(ext_neg, l - r)
        ext_pos = max(ext_pos, l - r)
    if 0 <= l - r:
        up.append((l - r, ext_neg, ext_pos))
    else:
        do.append((l - r, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (-tup[1], -tup[0]))
# print(up)
# print(do)

cur = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
for doi in do[::-1]:
    dif, ext_neg, ext_pos = doi
    if cur + ext_neg < 0:
        print("No")
        exit()
    cur += dif
if cur == 0:
    print("Yes")
else:
    print("No")