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())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    t = 0
    Life = 0
    R = 0
    while t<M:
        if S[t]=="(":
            Life += 1
        elif S[t]==")":
            if Life>=1:
                Life += -1
            else:
                R+=1
        t+=1
    LR[i][0] = Life #L
    LR[i][1] = R    # R

LP = 0
RP = 0
X = []
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        X.append([L,R,L-R])

X.sort(key=lambda x:x[2],reverse=True)

Life = LP
if Life==0:
    if (RP==0)and(len(X)==0):
        print("Yes")
    else:
        print("No")
else:
    flag = 1
    for i in range(len(X)):
        Life += -1*X[i][1]
        if (Life<0)and(X[i][0]-X[i][1]<0):
            flag=0
        Life += X[i][0]
    if flag==0:
        print("No")
    elif Life==RP:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    for __ in range(len(S)):
        if S[__] == '(':
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
        las = L[-1]
        mi = min(L)
    if las >= 0:
        Up.append((mi, las))
    else:
        Down.append((mi, las))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Wrong Answer

Solution code:
#!python3

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

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


def main():
    pl, ml = [], []
    for i in range(N):
        l = 0
        b = 0
        for s in S[i]:
            if s == "(":
                l += 1
            else:
                l -= 1
                b = min(b, l)
        if l > 0:
            pl.append((b, l))
        else:
            ml.append((l, b))
    pl.sort(reverse=True)
    ml.sort(reverse=True)

    x = 0
    for b, l in pl:
        if x + b < 0:
            print("No")
            return
        x += l
    for l, b in ml:
        if x + b < 0:
            print("No")
            return
        x += l
    
    if x == 0:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

score.sort(reverse=True)

cr = 0
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]

for n in range(N):
    if score[n][0] != 0 and sum(score[n]) >= 0:
        if cr + score[n][0] < 0:
            print("No")
            exit(0)
        cr += sum(score[n])

for n in range(N):
    if score[n][0] != 0 and sum(score[n]) < 0:
        cr += sum(score[n])
        if cr < 0:
            print("No")
            exit(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    t = 0
    Life = 0
    R = 0
    while t<M:
        if S[t]=="(":
            Life += 1
        elif S[t]==")":
            if Life>=1:
                Life += -1
            else:
                R+=1
        t+=1
    LR[i][0] = Life #L
    LR[i][1] = R    # R

LP = 0
RP = 0
X = []
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        X.append([L,R])

Life = LP
if Life==0:
    if (RP==0)and(len(X)==0):
        print("Yes")
    else:
        print("No")
else:
    for i in range(len(X)):
        Life += -1*X[i][1]
        Life += X[i][0]
    if Life==RP:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

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

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

score.sort(reverse=True)

cr = 0
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]

for n in range(N):
    if score[n][0] != 0 and sum(score[n]) > 0:
        if cr - score[n][0] < 0:
            print("No")
            exit(0)
        cr += sum(score[n])

for n in range(N):
    if score[n][0] != 0 and sum(score[n]) < 0:
        cr += sum(score[n])
        if cr < 0:
            print("No")
            exit(0)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
Ss = [input() for _ in range(N)]

r = 0
l = 0

for s in Ss:
  scr = 0
  for i in range(len(s)):
    if s[i] == '(':
      if scr < 0:
        r -= scr
        scr = 0
      scr += 1
    else:
      scr -= 1
  if scr > 0:
    l += scr
  elif scr < 0:
    r -= scr

if l == r:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key
n = int(input())
s = [input() for _ in range(n)]

def edge_info(s):
    pp = 0
    nn = 0

    for c in s:
        if c == '(':
            nn += 1
        else:
            if nn > 0:
                nn -= 1
            else:
                pp += 1

    return (nn, pp)

def comp(p1, p2):
    if p1[0] > p2[0]:
        return 1
    elif p1[1] < p2[1]:
        return -1
    return 0

edges = sorted([edge_info(ss) for ss in s], key=cmp_to_key(comp), reverse=True)
l_cnt = edges[0][0]

for l, r in edges[1:]:
    l_cnt -= r
    l_cnt += l

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

Submission status: Wrong Answer

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

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

score.sort(reverse=True)

cr = 0
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]

for n in range(N):
    if score[n][0] > 0:
        if cr - score[n][0] < 0:
            print("No")
            exit(0)
        cr += sum(score[n])

for n in range(N):
    if score[n][0] < 0:
        cr += sum(score[n])
        if cr < 0:
            print("No")
            exit(0)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import cmp_to_key
def resolve():
    n = int(input())
    S = [None] * n
    for i in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        S[i] = (min_balance, balance)

    def cmp(s1, s2):
        m1, b1 = s1
        m2, b2 = s2
        return -1 if min(m1, b1 + m2, 0) > min(m2, b2 + m1, 0) else 1

    S.sort(key = cmp_to_key(cmp))
    now = 0
    for min_balance, balance in S:
        if now + min_balance < 0:
            print("No")
            return
        now += balance

    print("Yes" if now == 0 else "No")
resolve()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)


if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
#L,R=lr[0]
dp=[defaultdict(int) for i in range(len(lr))]

stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()
    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        R=rlst-l
        L=llst-r

        if L==R and R>=0 and L>=0:
            print("Yes")
            exit()



print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  lst.append((b, h))
lst = sorted(lst, key=lambda x:x[1], reverse=True)
lst = sorted(lst, key=lambda x:x[0], reverse=True)

h = 0
b = 0
for i in range(n):
  if h + lst[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

# import numpy as np
# from itertools import *
# from collections import *

# S = input()
# N = int(input())
# K, N = [int(x) for x in input().split()]

N = int(input())

S = []
score = [(0,0)] * N

for n in range(N):
    S.append(input())
    while "()" in S[n]:
        S[n] = S[n].replace("()", "")

    if len(S[n]) >= 1:
        beg = S[n].count("(")
        end = S[n].count(")")

        if S[n][0] == "(":
            score[n] = (0, beg)
        else:
            score[n] = (-end, beg)
    else:
        score[n] = (0, 0)

cr = 0
for n in range(N):
    if score[n][0] == 0:
        cr += score[n][1]

for n in range(N):
    if score[n][0] > 0:
        cr += sum(score[n])

for n in range(N):
    if score[n][0] < 0:
        cr += sum(score[n])
        if cr < 0:
            print("No")
            exit(0)

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

Submission status: Wrong Answer

Solution code:









def     process(tab, first, end):
    #print(tab)
    #print(first, end)
    total = first
    for i in tab:
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
left = 0
right = 0
mid_right = 0
mid_left = 0
mid = ''

for _ in range(N):
	s = input()
	L = len(s)
	while True:
		s = s.replace('()', '')
		tmp = len(s)
		if tmp == L:
			break
		else:
			L = tmp
	
	if s:
		if L == 1:
			if s == '(':
				left += 1
			else:
				right += 1
		elif L > 1:
			if s[0] == s[-1]:
				if s[0] == '(':
					left += L
				else:
					right += L
			else:
				mid += s

mid_len = len(mid)
while True:
	mid = mid.replace('()', '')
	tmp = len(mid)
	if tmp == mid_len:
		break
	mid_len = tmp

for i in range(mid_len):
	if mid[i] == '(':
		mid_right = i
		mid_left = mid_len - i

if left < mid_right:
	print('No')
	sys.exit()
else:
	left -= mid_right

if right < mid_left:
	print('No')
	sys.exit()
else:
	right -= mid_left

if left == right:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  lst.append((b, h))

lst = sorted(lst, key=lambda x:x[0], reverse=True)
lst = sorted(lst, key=lambda x:x[1], reverse=True)
h = 0
b = 0
for i in range(n):
  if h + lst[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst[i][1]
if h == 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:









def     process(tab, first, end):
    print(tab)
    print(first, end)
    total = first
    for i in tab:
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(tab, first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
left = 0
right = 0
mid_right = 0
mid_left = 0
mid = 0

for _ in range(N):
	s = input()
	L = len(s)
	while True:
		s = s.replace('()', '')
		tmp = len(s)
		if tmp == L:
			break
		else:
			L = tmp
	
	if s:
		if L == 1:
			if s == '(':
				left += 1
			else:
				right += 1
		elif L > 1:
			if s[0] == s[-1]:
				if s[0] == '(':
					left += L
				else:
					right += L
			else:
				mid = 1
				for i in range(L):
					if s[i] == '(':
						mid_right += i
						mid_left += (L - i)
						break

if left < mid_right:
	print('No')
	sys.exit()
else:
	left -= mid_right

if right < mid_left:
	print('No')
	sys.exit()
else:
	right -= mid_left

if left == right:
	print('Yes')
else:
	print('No')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

import collections
buf = collections.deque()

def solve(S):
    for s in S:
        if buf:
            if s == ')':
                if buf[0] == '(':
                    buf.popleft()
                else:
                    buf.appendleft(s)

            else:
                buf.appendleft(s)

        else:
            buf.appendleft(s)

    ret = []
    while buf:
        ret.append(buf.pop())

    return ''.join(ret)


S = []
for _ in range(N):
    s = input()
    n = s.count('(') - s.count(')')
    S.append((s, n))
S.sort(reverse=True, key=lambda x: x[1])

S = ''.join([s[0] for s in S])
if len(solve(S)) == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]

for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1

    if l or r:
        lr.append([l,r])


idleR=10**8
stack=[]
def main(n,xl,xr):
    X=xl+idleR*xr
    #print(dp[n][X],n,xl,xr)
    if  not dp[n][X]:
        dp[n][X]=1
        stack.append([n,xl,xr])
    #    print(stack)
dp=[defaultdict(int) for i in range(len(lr))]
stack=[[-1,0,0]]
while stack:
    n,l,r=stack.pop()

    if n+1<len(lr):
        L,R=lr[n+1]

        if L-r>=0:
            main(n+1,l+L-r,R)
        else:
            main(n+1,l,R-(L-r))

        if R-l>=0:
            #print("a")
            #print(n+1,L,r+R-l)
            main(n+1,L,r+R-l)
        else:
            main(n+1,L-(R-l),r)

    else:
        #print(l,r)
        if l==r:
            print("Yes")
            exit()


print("No")

Submission status: Wrong Answer

Solution code:









def     process(tab, first, end):
    total = first
    #print(tab)
    for i in tab:
        total += i[0]
        if (total < 0):
            return ("No")
    if (total == end):
        return ("Yes")
    return ("No")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(sorted(tab), first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(input()) for i in range(N)]

A = [0 for i in range(N)]

for i in range(N):
    a = 0  #(の個数
    b = 0  #)の個数
    c = 0  #始点に対する最下点の高さ（(を+1,)を-1とみなす）
    for j in range(len(S[i])):
        if S[i][j] == '(':
            a += 1
            c = min(a - b, c)
        else:
            b += 1
            c = min(a - b, c)
    A[i] = (a-b,c)  #(何個高くなるか,最下点の相対的高さ)

from operator import itemgetter

B = []
C = []
for i in range(N):
    if A[i][0] >= 0:
        B.append(A[i])
    else:
        C.append(A[i])

B = sorted(B,key = itemgetter(1))

d = 0  #Bの元を全て繋げた時,何個高くなるか

for i in range(len(B)):
    if d + B[i][1] < 0:
        print('No')
        exit()
    else:
        d += B[i][0]

for i in range(len(C)):
    C[i] = (-C[i][0],C[i][1]-C[i][0])

C = sorted(C,key = itemgetter(1))

e = 0

for i in range(len(C)):
    if e + C[i][1] < 0:
        print('No')
        exit()
    else:
        e += C[i][0]

if d == e:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
s = [input() for _ in range(n)]
x = []
y = []
for i in range(n):
    cnt = 0
    for j in range(len(s[i])):
        if s[i][j] == '(':
            cnt += 1
        else:
            cnt -= 1
    if cnt >= 0:
        x.append([len(s[i]), cnt, s[i]])
    else:
        y.append([len(s[i]), cnt, s[i]])
x.sort(key=lambda x:(x[0], x[1]))
y.sort(key=lambda x:(x[0], -x[1]))
flag = False
tmp = 0
que = deque()
for _, _, i in x:
    if not flag:
        if i[0] == '(':
            flag = True
            for j in i:
                if j == '(':
                    tmp += 1
                else:
                    if tmp > 0:
                        tmp -= 1
                    else:
                        print('No')
                        quit()
            while que:
                i = que.popleft()
                for j in i:
                    if j == '(':
                        tmp += 1
                    else:
                        if tmp > 0:
                            tmp -= 1
                        else:
                            print('No')
                            quit()
        else:
            que.append(i)
    else:
        for j in i:
            if j == '(':
                tmp += 1
            else:
                if tmp > 0:
                    tmp -= 1
                else:
                    print('No')
                    quit()
for _, _, i in y:
    for j in i:
        if j == '(':
            tmp += 1
        else:
            if tmp > 0:
                tmp -= 1
            else:
                print('No')
                quit()
if tmp != 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
l = 0
r = 0
cntl = 0
cntr = 0
fl = 0
fr = 0
exl = 0
exr = 0
only_r = 0
only_l = 0
maxl = 0
maxr = 0
exlr = []
for i in range(n):
    s = input()
    templ = 0
    tempr = 0
    temp_exl = 0
    temp_exr = 0
    fl = 0
    fr = 0
    for i in s:
        if i == "(":
            tempr += 1
        elif i == ")":
            tempr -= 1
            if tempr < 0:
                tempr = 0
                templ += 1
                fl = 1
    temp_exl += templ
    if tempr > 0:
        temp_exr += tempr
        fr = 1
    if fl == 1 and fr == 0:
        only_l += temp_exl
    elif fr == 1 and fl == 0:
        only_r += temp_exr
    elif temp_exl + temp_exr > 0:
        exl += temp_exl
        exr += temp_exr
        exlr.append([temp_exl-temp_exr, temp_exl,temp_exr])
    # maxl = max(maxl,temp_exl)
    # maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
a = only_r
b = only_l
# exlr.sort()
exlr.sort(key=lambda x: x[1])

# print(exlr)
for i in range(len(exlr)):
    if exlr[i][1] <= a and exlr[i][0] <= 0:
        a -= exlr[i][0]
        exlr[i] = [0,0,0]
# print(exlr)
for i in exlr:
    a -= i[1]
    if a<0:
        print("No")
        exit()
    a += i[2]
if a-b == 0:
    print("Yes")
else:
    print("No")
# if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0:
#     print("Yes")
# elif exr+exl+only_l+only_r == 0:
#     print("Yes")
# else:
#     print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [list(input()) for i in range(N)]

A = [0 for i in range(N)]

for i in range(N):
    a = 0  #(の個数
    b = 0  #)の個数
    c = 0  #始点に対する最下点の高さ（(を+1,)を-1とみなす）
    for j in range(len(S[i])):
        if S[i][j] == '(':
            a += 1
            c = min(a - b, c)
        else:
            b += 1
            c = min(a - b, c)
    A[i] = (a-b,c)  #(何個高くなるか,最下点の相対的高さ)

from operator import itemgetter

B = []
C = []
for i in range(N):
    if A[i][0] >= 0:
        B.append(A[i])
    else:
        C.append(A[i])

B = sorted(B,key = itemgetter(1))

d = 0  #Bの元を全て繋げた時,何個高くなるか

for i in range(len(B)):
    if d + B[i][1] < 0:
        print('No')
        exit()
    else:
        d += B[i][0]

for i in range(len(C)):
    C[i] = (-C[i][0],C[i][1]-C[i][0])

e = 0

for i in range(len(C)):
    if e + C[i][1] < 0:
        print('No')
        exit()
    else:
        e += C[i][0]

if d == e:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:









def     process(tab, first, end):
    total = first
    #print(tab)
    for i in tab:
        total += i[0]
        if (total < 0):
            return ("No")
    return ("Yes")




N  = int(input())

first = -1
last = -1
clean = 0
tab = []
total = 0
for i in range(N):
    s = input()
    avant = 0
    apres = 0
    for j in s:
        if (j == '('):
            apres += 1
        elif (j == ')'):
            if (apres > 0):
                apres -= 1
            else:
                avant += 1
    if (avant == 0 and apres > 0 and first == -1):
        first = apres
    elif (apres == 0 and avant > 0 and last == -1):
        last = avant
    elif (avant > 0 or apres > 0):
        tab.append((apres - avant, avant, apres, s))
    else:
        clean += 1
    total += avant - apres
if (first == -1 and clean > 0):
    first = 0
    clean -= 1
if (last == -1 and clean > 0):
    last = 0


tab = sorted(tab)
tab = tab[::-1]
if (total == 0 and first > -1 and last > -1):
    res = process(sorted(tab), first, last)
else:
    if (total == 0 and N == 1):
        res = "Yes"
    else:
        res = "No"
print(res)

Submission status: Wrong Answer

Solution code:
dicpos = {}
dicneg = {}

N = int(input())
for i in range(N):
  buf = [0]
  for s in input():
    if s=="(":
      buf.append(buf[-1] + 1)
    else:
      buf.append(buf[-1] - 1)
  low = min(buf)
  last = buf[-1]
  if last>0:
    if low in dicpos:
      dicpos[low].append(last)
    else:
      dicpos[low] = [last]
  else:
    if low-last in dicneg:
      dicneg[low-last].append(-last)
    else:
      dicneg[low-last] = [-last]
neg_sorted = sorted(dicneg.items(), key=lambda x:x[0], reverse=True)
pos_sorted = sorted(dicpos.items(), key=lambda x:x[0], reverse=True)
summ = 0
flag = 0
for i in pos_sorted:
  for j in i[1]:
    if summ + i[0] < 0:
      flag = 1
      print("No")
      break
    summ += j
summ2 = 0
if flag == 0:
  for i in neg_sorted:
    for j in i[1]:
      if summ2 + i[0] < 0:
        flag = 1
        print("No")
        break
      summ2 += j
if flag == 0:
  if summ == summ2:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)

l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  l += -hpop(h)
  r = br(tt, l)
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
  if h[0] >= 0:
    if c < N:
      print("No")
      exit(0)
    break
  cc += 1
for i in range(c, N): hpush(h, t[i][0] - t[i][1])
while len(h): l += -h.pop()
if l == 0: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = []
tt = []
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": rs[x] += 1
    if S[i] == ")":
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
  t.append((ls[x], rs[x]))
  tt.append(ls[x])
t.sort()
tt.sort()
if sum(ls) != sum(rs):
  print("No")
  exit(0)

l = 0
c = 0
cc = 0
h = []
while cc < N:
  r = br(tt, l)
  i = c
  while i < r:
    hpush(h, t[i][0] - t[i][1])
    i += 1
  c = i
  if len(h) == 0:
    if c < N:
      print("No")
      exit(0)
  if h[0] >= 0:
    if c < N:
      print("No")
      exit(0)
    break
  l += -hpop(h)
  cc += 1
for i in range(c, N): hpush(h, t[i][0] - t[i][1])
while len(h): l += -h.pop()
if l == 0: print("Yes")
else: print("No")