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())
l=[]
flags=0
flagg=0
flag1s=0
flag1g=0
count=0

for i in range(N):
  c=[0,0]
  a=input()
  A=[]
  for i in a:
    A.append(str(i))
    if i=="(":
      count+=1
    else:
      count-=1  
  if A[0]==")":
    if c[1]==0:
      flag1s=1
      c[1]=1
  if A[0]=="(":
    if c[0]==0:
      flags=1
      c[0]=1
  if A[len(A)-1]==")":
    if c[0]==0:
      flagg=1
      c[0]=1
  if A[len(A)-1]=="(":
    if c[1]==0:
      flag1g=1
      c[1]=1
  
  if A[0]==")":
    if flag1s==0:
      flag1s=1
if ((flags==1 and flagg==1) or (flag1s==1 and flag1g==1)) and count==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = deque([])
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res.append(m)
    ##print(res)
    try:
        a = min(res)
    except:
        a = m
    return [a,m]

N = int(input())
S = [check() for _ in range(N)]
print(S)
S.sort(reverse=True)

a = 0
b = 0

for res,m in S:
    a += res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
n=int(input())
m=[]
for i in range(n):
  s=input()
  a,t=0,0
  # a:左に(がいくつ必要か
  # t: (のストック i.e. 右に)がいくつ必要か
  for j in s:
    if t==0 and j==")":
      a+=1
    elif j=="(":
      t+=1
    elif t>0 and j==")":
      t-=1
  m.append([a,t])
  #[ 左に(がいくつ必要か, 右に)がいくつ必要か ]
m.sort()
for i in range(n):
  if m[n-1-i][1]==0:
    M=m[n-1-i]
    del m[n-1-i]
    m.append(M)
    break
r=0 # (のストック
if m[0][0]!=0 or m[-1][-1]!=0:
  print("No")
  exit()
for li in m:
  r+=li[1]-li[0]
  if r<0:
    print("No")
    exit()
if r==0:
  print("Yes")
else:
  print("No")
#print(m)

Submission status: Wrong Answer

Solution code:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_l = 0
sum_r = 0
nokori_l = 0
nokori_r = 0
for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        sum_l1 = sum_l
        sum_r1 = r
        mid1 = sum_r + l
        if mid1 < 0:
            sum_l1 += mid1
        else:
            sum_r1 += mid1

        sum_l2 = l
        sum_r2 = sum_r
        mid2 = r + sum_l
        if mid2 < 0:
            sum_l2 += mid2
        else:
            sum_r2 += mid2

        if sum_r2 <= sum_r1:
            sum_l = sum_l2
            sum_r = sum_r2
        else:
            sum_l = sum_l1
            sum_r = sum_r1
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

right_side = sum_r + nokori_l
left_side = nokori_r + sum_l

if left_side >= 0 and right_side <= 0:
    if left_side + right_side == 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N=int(input())
l=[]
flags=0
flagg=0
flag1s=0
flag1g=0
count=0

for i in range(N):
  c=[0,0]
  a=input()
  A=[]
  for i in a:
    A.append(str(i))
    if i=="(":
      count+=1
    else:
      count-=1  
  if A[0]==")":
    if c[1]==0:
      flag1s=1
      c[1]=1
  if A[0]=="(":
    if c[0]==0:
      flags=1
      c[0]=1
  if A[len(A)-1]==")":
    if c[0]==0:
      flagg=1
      c[0]=1
  if A[len(A)-1]=="(":
    if c[1]==0:
      flag1g=1
      c[1]=1
  
  if A[0]==")":
    if flag1s==0:
      flag1s=1
  print(flags,flagg,flag1s,flag1g)
if ((flags==1 and flagg==1) or (flag1s==1 and flag1g==1)) and count==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
input = raw_input

n = int(input())

def f(s):
    l = 0
    n = len(s)
    si = None
    for i in range(n):
        if s[i] == ")":
            l -= 1
        else:
            si = i
            break
    r = 0
    if si is None:
        pass
    else:
        for i in range(si, n):
            if s[i] == "(":
                r += 1
            else:
                r -= 1
    return l, r


ind = 0
pairs = []
ls = []
rs = []

sum_l = 0
sum_r = 0
nokori_l = 0
nokori_r = 0
for i in range(n):
    s = input()
    l, r = f(s)
    if l == 0 and r == 0:
        continue
    elif l != 0 and r != 0:
        sum_l1 = sum_l
        sum_r1 = r
        mid1 = sum_r + l
        if mid1 < 0:
            sum_l1 += mid1
        else:
            sum_r1 += mid1

        sum_l2 = l
        sum_r2 = sum_r
        mid2 = r + sum_l
        if mid2 < 0:
            sum_l2 += mid2
        else:
            sum_r2 += mid2

        if sum_r2 <= sum_r1:
            sum_l = sum_l2
            sum_r = sum_r2
        else:
            sum_l = sum_l1
            sum_r = sum_r1
    else:
        if l != 0:
            nokori_l += l
        else:
            nokori_r += r

print(nokori_r, sum_l, sum_r, nokori_l)
right_side = sum_r + nokori_l
left_side = nokori_r + sum_l

if left_side >= 0 and right_side <= 0:
    if left_side + right_side == 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

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([l,r-l])

sei.sort(key=lambda x: (x[0],-x[1]))
hu.sort(key=lambda x: -(x[1]-x[0]))
tmp=0

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline().strip()

def check():
    s = input()
    m = 0
    res = deque([])
    for i in s:
        if i == "(":
            m += 1 
        else:
            m -= 1
            res.append(m)
    try:
        a = min(res)
    except:
        a = m
    return [m,m]

N = int(input())
S = [check() for _ in range(N)]
##print(S)
S.sort(reverse=True)

a = 0
b = 0

for res,m in S:
    a += res
    b += m
    if a < 0:
        print("No")
        exit()

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

Submission status: Wrong Answer

Solution code:
# あらかじめ前処理すれば、
# 1: (((...
# 2: )))...
# 3: ...)(((..
# のいずれかの形式に出来る
# typeでソートして、1, 3, 2の形にして解決していけるかを調べれば良さそう？
# "))(", ")))((("とかが険しい
# ほんまか？なんかいけそう
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)

def remove(s):
    while True:
        if len(s) <= 0:
            break
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

n = int(input())
s = [[], [], []]
for i in range(n):
    s_ = remove(input())
    t1 = s_.count("(")
    t2 = s_.count(")")
    if t1 > 0 and t2 > 0:
        s[1].append(s_)
    elif t1 > 0:
        s[0].append(s_)
    else:
        s[2].append(s_)
s[1] = sorted(s[1])
for i in range(3):
    s[i] = "".join(s[i])

s = "".join(s)
s = remove(s)
if len(s) == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def check(pt, brackets):
    brackets.sort(reverse=True)
    for m, t in brackets:
        if pt + m < 0:
            return False
        pt += t
    return pt


n = int(input())
brackets_p = []  # (始めを0として、( = +1, ) = -1 として、最後はいくつか, 途中の最小値はいくつか)
brackets_m = []
pt = 0
mt = 0
for _ in range(n):
    s = input()
    total = 0
    mini = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1
            mini = min(mini, total)

    if total >= 0:
        if mini == 0:
            pt += total
        else:
            brackets_p.append((mini, total))
    else:
        total, mini = -total, mini - total
        if mini == 0:
            mt += total
        else:
            brackets_m.append((mini, total))

pt = check(pt, brackets_p)
mt = check(mt, brackets_m)

if (pt == False) or (mt == False) or (pt != mt):
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:

n = int(input())
list1 = []
list2 = []
for i in range(n):
    s = input()
    list1.append(s)
for j in list1:
    if j[:1]*(len(j)//2) + j[-2:]*(len(j)//2) == j or j[len(j)//2:] + j[:len(j)//2] == j:
        list1.remove(j)
for o in list1:
    for k in o:
        list2.append(k)
m = (sorted(list2))
if m[len(m)//2:] + m[:len(m)//2] == m:
    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)]
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 llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])

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

for l,r in stack:
    if l<=rlst:

        L=rlst-l
        l=0
    else:
        continue
    if r<=llst:

        R=llst-r
        r=0
    else:
        continue

    if L-R==0:
        print("Yes")
        exit()
    else:
        continue
print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
lst_1_any_hihu = []
lst_1_hihu_hu = []
lst_1_hu_hu = []
lst_0_any_hihu = []
lst_0_hihu_hu = []
lst_0_hu_hu = []
for i in range(n):
    si = input()
    s.append(si)
    if si[0] == '(': start = 1
    else: start = 0
    ruikei = 0
    mini = 0
    for moji in si:
        if moji == '(':
            ruikei += 1
        else:
            ruikei -= 1
        mini = min(mini, ruikei)
    if start == 1:
        if mini >= 0:
            lst_1_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_1_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_1_hu_hu.append([start, ruikei, mini, i])
    else:
        if mini >= 0:
            lst_0_any_hihu.append([start, ruikei, mini, i])
        elif ruikei >= 0:
            lst_0_hihu_hu.append([start, ruikei, mini, i])
        else:
            lst_0_hu_hu.append([start, ruikei, mini, i])

lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[1])
lst_1_hihu_hu.sort(reverse=True, key=lambda x: x[2])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[1])
lst_0_hihu_hu.sort(reverse=True, key=lambda x: x[2])

now = 0
for lst in lst_1_any_hihu:
    now += lst[1]
for lst in lst_1_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_any_hihu:
    now += lst[1]
for lst in lst_0_hihu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_1_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
for lst in lst_0_hu_hu:
    si = s[lst[3]]
    for i in range(len(si)):
        if si[i] == '(':
            now += 1
        else:
            now -= 1
            if now < 0:
                print('No')
                exit()
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for i in range(n):
    a = input()
    b = []
    for j in range(len(a)):
        if a[j]=='(':
            b.append(1)
        else:
            b.append(-1)
    s.append(b)

a = []
for x in s:
    b = 0
    c = 0
    for y in x:
        c+=y
        b = min(b,c)
    l = len(x)
    d = 0
    e = 0
    for j in range(l):
        e += x[l-j-1]
        d = max(d,e)

    a.append([c,b,d])

a.sort()
l = []
r = []
for i in range(n):
    c,b,d = a[i]
    if c>=0:
        l.append([b,c])
    else:
        r.append([d,c])

l.sort()
r.sort()

flag = 1
x = 0
while l:
    b,c = l.pop()
    x += c
    if x+b<0:
        flag = 0
y = 0
for d,c in r:
    y += c
    if y+d>0:
        flag = 0


if y+x!=0:
    flag = 0
print('Yes' if flag else'No')

Submission status: Wrong Answer

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

s = [0]*N
m = [len(S[i]) for i in range(N)]
for i, x in enumerate(S):
    tmp = 0
    for j in range(len(x)):
        if x[j] == '(':
            tmp += 1
        else:
            tmp -= 1
            m[i] = min(tmp, m[i])
    s[i] = tmp

if sum(s) == 0:
    ss = [(S[i], m[i], s[i]) for i in range(N)]
    ss.sort(key=lambda x: (x[1], x[2]), reverse=True)
    tmp = 0
    for x, _, _ in ss:
        for z in x:
            if z == '(':
                tmp += 1
            else:
                tmp -= 1
                if tmp < 0:
                    print("No")
                    exit(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
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
    else:
        exl += temp_exl
        exr += temp_exr
    maxl = max(maxl,temp_exl)
    maxr = max(maxr,temp_exr)
# print (exr,exl,only_r,only_l)
if exl+only_l == exr+only_r and exl-exr == only_r-only_l and only_l > 0 and only_r > 0 and maxl<=only_r and maxr <= only_l:
    print("Yes")
elif exr+exl+only_l+only_r == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
import sys;input=sys.stdin.readline
X = []
Y = []
for _ in range(N):
    s = input().strip()
    a, b = 0, 0
    for c in s:
        if c == "(":
            a += 1
        else:
            if a > 0:
                a -= 1
            else:
                b += 1
    if a >= b:
        X.append((a, b))
    else:
        Y.append((b, a))
X.sort(key=lambda x:x[0]-x[1])
Y.sort(key=lambda x:x[0]-x[1])
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
while stack:
    a, b = stack[-1]
    if b <= s:
        s += a-b
        stack.pop()
        continue
    break
X = Y
st = s
if stack:
    st = 10**19
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
while stack:
    a, b = stack[-1]
    if b <= s:
        s += a-b
        stack.pop()
        continue
    break
if stack:
    s = -10**19
#print(s, st)
if len(stack) > 0 or s != st:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = [input() for i in range(n)]
    s = []
    for i in range(n):
        p = 0
        m = 0
        for j in a[i]:
            if j == "(":
                p += 1
            else:
                p -= 1
            if p < m:
                m = p
        s.append((p,m))
    s.sort(reverse = True)
    q = []
    k = 0
    i = 0
    while q or (i < n):
        while i < n and s[i][1]+k >= 0:
            heappush(q,-s[i][0])
            i += 1
        if not q:
            print("No")
            return
        k -= heappop(q)
        if k < 0:
            print("No")
            return
    if q or k != 0 or i < n:
        print("No")
    else:
        print("Yes")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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[1] >= temp[0]:
            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: Wrong Answer

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

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 = False, 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: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
S=[]
for i in range(N):
    S.append(list(input()))
nL=0
nR=0
SLR=[]

for i in range(N):
    s=S[i]
    l=0
    r=0
    for j in range(len(s)):
        if s[j]==")":
            nL+=1
            if r==0:
                l+=1
            else:
                r-=1
        else:
            nR+=1
            r+=1
    SLR.append([l,r])

RR=0
LL=0
L=0
R=0

for i in range(N):
    if SLR[i][0]==0:
        RR+=SLR[i][1]
    elif SLR[i][1]==0:
        LL+=SLR[i][0]
    else:
        L1=L+max(0,SLR[i][0]-R)
        R1=max(0,R-SLR[i][0])+SLR[i][1]
        L2=SLR[i][0]+max(0,L-SLR[i][1])
        R2=R+max(0,SLR[i][1]-L)
        
        if L1+R1<L2+R2:
            L=L1
            R=R1
        else:
            L=L2
            R=R2

if nR==nL and RR>=L and LL>R:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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


def main():
    N = int(input())
    S = []
    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)
        S.append((max_depth, height - max_depth))
    S.sort(key=lambda x: (x[0], x[1]))

    height = 0
    if S[-1][0] != 0:
        print("No")
        return
    while S:
        d, h = S.pop()
        #print("({}, {})".format(d, h))
        if height + d < 0:
            print("No")
            return
        height += d+h
    if height != 0: print("No")
    else: print("Yes")





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    l = []
    n = int(input())
    s = []
    for i in range(n):
        s.append(input())
    for string in s:
        top = -1
        sb = []
        for c in string:
            if len(sb) == 0:
                sb.append(c)
                top+=1
            else:
                if c == '(':
                    sb.append(c)
                    top+=1
                else:
                    if sb[top] == '(':
                        sb.pop()
                        top-=1
                    else:
                        sb.append(c)
        start = 0
        end = 0
        i = 0
        while i<len(sb) and sb[i] == ')':
            start+=1
            i+=1
        while i<len(sb) and sb[i] == '(':
            end+=1
            i+=1
        if start == 0 and end == 0:
            pass
        else:
            l.append((start,end))
    
    sz = False
    ez = False
    sums = 0
    sume = 0
    for t in l:
        if t[0] == 0:
            sz = True
        if t[1] == 0:
            ez = True

        sums += t[0]
        sume += t[1]
    if not sz:
        print("No")
        exit()
    if not ez:
        print("No")
        exit()
    
    if sums == sume:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())

stats = defaultdict(list)
key_set = set()
for i in range(n):
    s = input().rstrip()

    neg = 0
    pos = 0
    for v in s:
        if v == '(':
            pos += 1
        else:
            if pos > 0:
                pos -= 1
            else:
                neg += 1
    stats[neg].append((pos-neg, neg, pos))
    key_set.add(neg)

key_list = sorted(list(key_set))

for i in stats.keys():
    stats[i].sort()

cur = 0
for i in range(n):
    max_diff = -1 * (10 ** 10)
    v_index = -1
    for j in range(len(key_list)):
        if key_list[j] > cur:
            break

        if len(stats[key_list[j]]) > 0:
            diff, neg, pos = stats[key_list[j]][-1]
            if diff > max_diff:
                max_diff = diff
                v_index = j

    if v_index < 0:
        print('No')
        exit()

    diff, neg, pos = stats[key_list[v_index]][-1]

    if cur < neg:
        print('No')
        exit()

    cur = cur - neg + pos
    del stats[key_list[v_index]][-1]

if cur == 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

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
    else:
        exl += temp_exl
        exr += temp_exr
# print (exr,exl,only_r,only_l)
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, = map(int, input().split())
import sys;input=sys.stdin.readline
X = []
Y = []
for _ in range(N):
    s = input().strip()
    a, b = 0, 0
    for c in s:
        if c == "(":
            a += 1
        else:
            if a > 0:
                a -= 1
            else:
                b += 1
    if a >= b:
        X.append((a, b))
    else:
        Y.append((b, a))
X.sort(key=lambda x:x[0]-x[1])
Y.sort(key=lambda x:x[0]-x[1])
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
while stack:
    a, b = stack[-1]
    if b <= s:
        s += a-b
        stack.pop()
        continue
    break
X = Y
st = s
s = 0
stack = []
while X:
    a, b = X.pop()
    if b > s:
        stack.append((a, b))
        continue
    s += a-b
    while stack:
        a, b = stack[-1]
        if b <= s:
            s += a-b
            stack.pop()
            continue
        break
while stack:
    a, b = stack[-1]
    if b <= s:
        s += a-b
        stack.pop()
        continue
    break
#print(s, st)
if len(stack) > 0 or s != st:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())

demand_dic = {}

open_list = set()

for i in range(n):
    s = input()
    need_open = 0
    need_close = 0
    for j in range(len(s)):
        if s[j] == ")":
            if need_close > 0:
                need_close -= 1
            else:
                need_open += 1
        if s[j] == "(":
            need_close += 1

    if demand_dic.get(need_open, None) is None:
        demand_dic[need_open] = []
    heapq.heappush(demand_dic[need_open], -(need_close - need_open))
    open_list.add(need_open)

yn_answer = "No"

end = False

can_close = 0
remain = 0

for k in open_list:
    needs = demand_dic[k]
    for i in range(len(needs)):
        if k > can_close:
            end = True
            break
        else:
            change = - heapq.heappop(needs)
            if change >= 0:
                can_close += change
            else:
                remain -= change
    if end:
        break

if not end and can_close - remain == 0:
    yn_answer = "Yes"

print(yn_answer)

Submission status: Wrong Answer

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

l = []
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2!=0:
        l.append([n1,n2])

l.sort(key=lambda x:x[0]-x[1])
l.sort(key=lambda x:x[0])

n = 0
ans = 'Yes'
for i in range(len(l)):
    n1,n2 = l[i]
    if n < n1:
        ans = 'No'
        break
    n -= n1
    n += n2
if n > 0:
    ans = 'No'
print(ans)