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: Time Limit Exceeded

Solution code:
cnt=0
def check(a,b):
    global cnt
    for i in range(len(a)):
        cnt-=a[i][0]
        if cnt<0:
            return False
        cnt+=a[i][1]

    for i in range(len(b)):
        cnt-=b[i][0]
        if cnt<0:
            return False
        cnt+=b[i][1]
    if cnt==0:
        return True
    return False

a=[]
b=[]
for i in range(int(input())):
    s=list(input())
    ans=[]
    for j in range(len(s)):
        if s[j]=='(':
            ans.append('(')
        else:
            if len(ans)==0:
                ans.append(')')
                continue
            if ans[-1]=='(':
                ans.pop(-1)
            else:
                ans.append(')')
    L=0

    for j in range(len(ans)):
        if ans[j]==')':
            L+=1
        else:
            break
    R=len(ans)-L
    if L<R:
        a.append((L,R))
    else:
        b.append((L,R))

    a.sort()
    b.sort(key=lambda x:x[1],reverse=True)
    #print(a,b)
if check(a,b):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
cnt=0
def check(a,b):
    global cnt
    for i in range(len(a)):
        cnt-=a[i][0]
        if cnt<0:
            return False
        cnt+=a[i][1]

    for i in range(len(b)):
        cnt-=b[i][0]
        if cnt<0:
            return False
        cnt+=b[i][1]
    if cnt==0:
        return True
    return False

a=[]
b=[]
for i in range(int(input())):
    s=list(input())
    ans=[]
    for j in range(len(s)):
        if s[j]=='(':
            ans.append('(')
        else:
            if len(ans)==0:
                ans.append(')')
                continue
            if ans[-1]=='(':
                ans.pop(-1)
            else:
                ans.append(')')
    L=0

    for j in range(len(ans)):
        if ans[j]==')':
            L+=1
    R=len(ans)-L
    if L<R:
        a.append((L,R))
    else:
        b.append((L,R))
    a.sort()
    b.sort(key=lambda x:x[1],reverse=True)
    #print(a,b)
if check(a,b):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
Line = namedtuple('Line', ['lowest', 'end'])


def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        now = 0
        lowest = 0
        for c in s:
            if c == "(":
                now += 1
            else:
                now -= 1
                lowest = min(lowest, now)
        if now > 0:
            up_lines.append(Line(lowest, now))
        else:
            down_lines.append(Line(lowest-now, -now))
    up_lines.sort(key=lambda line: -line.lowest)
    down_lines.sort(key=lambda line: -line.lowest)
    left = 0
    for line in up_lines:
        if left + line.lowest < 0:
            print("No")
            return
        left += line.end
        if left < 0:
            print("No")
            break
    right = 0
    for line in down_lines:
        if right + line.lowest < 0:
            print("No")
            return
        right += line.end
        if right < 0:
            print("No")
            break
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import namedtuple
Line = namedtuple('Line', ['lowest', 'end'])


def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        now = 0
        lowest = 0
        for c in s:
            if c == "(":
                now += 1
            else:
                now -= 1
                lowest = min(lowest, now)
        if now > 0:
            up_lines.append(Line(lowest, now))
        else:
            down_lines.append(Line(lowest-now, -now))
    up_lines.sort(key=lambda line: -line.end)
    up_lines.sort(key=lambda line: -line.lowest)
    down_lines.sort(key=lambda line: -line.end)
    down_lines.sort(key=lambda line: -line.lowest)
    left = 0
    for line in up_lines:
        if left + line.lowest < 0:
            print("No")
            return
        left += line.end
        if left < 0:
            print("No")
            break
    right = 0
    for line in down_lines:
        if right + line.lowest < 0:
            print("No")
            return
        right += line.end
        if right < 0:
            print("No")
            break
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
scop = [] #高低差,min値
scom = []
scomn = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif sa == ms:
        scomn.append([ms,sa])
    else:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = []
M = []
for i in range(N):
    S = input()
    L = [0, 0]
    pos = 0
    for i in range(len(S)):
        if S[i] == '(':
            pos += 1
        else:
            pos -= 1
            if L[0] > pos:
                L[0] = pos
    L[1] = pos
    if L[1] < 0:
        M.append([L[0]-L[1], -L[1]])
    elif L[1] == 0:
        if L[0] < 0:
            M.append([L[0]-L[1], -L[1]])
        else:
            P.append(L)
    else:
        P.append(L)
P.sort(reverse=True)
M.sort(reverse=True)
flgL, flgR = True, True
l, r = len(P), len(M)
pp, pm = 0, 0
for i in range(l):
    if P[i][0] + pp < 0:
        flgL = False
        break
    else:
        pp += P[i][1]
for i in range(r):
    if M[i][0] + pm < 0:
        flgR = False
        break
    else:
        pm += M[i][1]
if pp == pm and flgL and flgR:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# F

N = int(input())

import bisect
list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        index = bisect.bisect_right(list_plus, [min_state, state])
        list_plus.insert(index, [min_state, state])
        # list_plus.append([min_state, state])
    else:
        index = bisect.bisect_right(list_minus, [min_state - state, -state])
        list_minus.insert(index, [min_state - state, -state])
        # list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0

    for min_state, state in arr[-1::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

total_state_plus = compute(list_plus)
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Time Limit Exceeded

Solution code:
# F

N = int(input())

import bisect
list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        index = bisect.bisect_right(list_plus, [min_state, state])
        list_plus.insert(index, [min_state, state])
        # list_plus.append([min_state, state])
    else:
        index = bisect.bisect_right(list_minus, [min_state - state, -state])
        list_minus.insert(index, [min_state - state, -state])
        # list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0

    for min_state, state in arr[-1::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Time Limit Exceeded

Solution code:
# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append([min_state, state])
    else:
        
        list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0

    for min_state, state in arr[-1::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Time Limit Exceeded

Solution code:
# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append([min_state, state])
    else:
        
        list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Time Limit Exceeded

Solution code:
# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state >= 0:
        list_plus.append([min_state, state])
    else:
        list_minus.append([min_state - state, -state])

list_plus.sort()
total_state_plus = 0
for min_state, state in list_plus[::-1]:
    if total_state_plus + min_state < 0:
        print('No')
        exit()
    else:
        total_state_plus += state

list_minus.sort()
total_state_minus = 0
for min_state, state in list_minus[::-1]:
    if total_state_minus + min_state < 0:
        print('No')
        exit()
    else:
        total_state_minus += state

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

pdat=[]
mdat=[]

for i in range(n):
    s=input()
    
    mini=0
    now=0
    for q in range(len(s)):
        if s[q]=="(":
            now+=1
        else:
            now-=1
            mini=(min(mini,now))
    if now>=0:
        pdat.append((now,mini,mini-now))
    else:
        mdat.append((now,mini,mini-now))

pdat.sort(key=lambda x:-x[1])
mdat.sort(key=lambda x:x[2])

now=0
for d in pdat+mdat:
    if now+d[1]<0:
        print("No")
        break
    now+=d[0]
else:
    if now==0:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

pdat=[]
mdat=[]

for i in range(n):
    s=input()
    
    mini=0
    now=0
    for q in range(len(s)):
        if s[q]=="(":
            now+=1
        else:
            now-=1
            mini=(min(mini,now))
    if now>=0:
        pdat.append((now,mini,mini-now))
    else:
        mdat.append((now,mini,mini-now))

pdat.sort(key=lambda x:-x[1])
mdat.sort(key=lambda x:x[2])
pdat.extend(mdat)

now=0
for d in pdat:
    if now+d[1]<0:
        print("No")
        break
    now+=d[0]
else:
    if now==0:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
from itertools import accumulate,chain
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    bm = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    Sp.append([bm, 0])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def check(li):
    b = 0
    for eb, eh in li:
        if b + eb < 0:
            return False

        b += eh

    return True


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

l = []
r = []
sm = 0
for word in s:
    h = 0
    b = 0
    for e in word:
        if e == "(":
            h += 1
        else:
            h -= 1

        b = min(b, h)

    if h > 0:
        l.append([b, h])
    else:
        r.append([b-h, -h])

    sm += h

l.sort(reverse=True)
r.sort(reverse=True)

if check(l) and check(r) and sm == 0:
    ans = "Yes"
else:
    ans = "No"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
from itertools import accumulate,chain
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    bm = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    #if h == 0 and b < 0:
     # bm = min(bm, b)
    if h >= 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    mi=min(itertools.accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))
    st[i].append(mi)

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v,w=list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
#print(now2)
for vsub in v:
    if now2+vsub[1]<0:
        print("No")
        sys.exit()
    now2+=vsub[0]
for wsub in w:
    if now2+wsub[1]<0:
        print("No")
        sys.exit()
    now2+=wsub[0]
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if not p:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if not m:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  if len(Sp) < len(Sm):
    Sp.sort(reverse=True)
    p = check(Sp)
    if not p:
      print('No')
      exit()
    Sm.sort(reverse=True)
    m = check(Sm)
    if not m:
      print('No')
      exit()
  else:
    Sm.sort(reverse=True)
    m = check(Sm)
    if not m:
      print('No')
      exit()
    Sp.sort(reverse=True)
    p = check(Sp)
    if not p:
      print('No')
      exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    u = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      u = min(u, h)
    if h > 0:
      Sp.append([u, h])
    else:
      Sm.append([u-h, -h])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(reverse=True)
  p = check(Sp)
  if not p:
    print('No')
    exit()
  Sm.sort(reverse=True)
  m = check(Sm)
  if not m:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def init():
    global N, Sp, Sm, total
    N = int(input())
    Sp = []
    Sm = []
    total = 0
    for i in range(N):
      l = input()
      u = 0
      h = 0
      for j in range(len(l)):
        if l[j] == '(':
          h += 1
        else:
          h -= 1
        if h < u:
          u = h
      if h >= 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
      total += h
    Sp.sort(reverse=True)
    Sm.sort(reverse=True)

def main():
  init()
  if total != 0:
    print('No')
  else:
    p = check(Sp)
    m = check(Sm)
    if p and m:
      print('Yes')
    else:
      print('No')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return False
    else:
      h += S[i][1]
  return True

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
x, y = [], []
for _i in range(n):
    s = input()
    p = 0
    m = 0
    for j in range(len(s)):
        if s[j]=="(":
            p += 1
        else:
            p -= 1
            m, _m = sorted([p, m])
    if p > 0:
        x.append([m, p])
    else:
        y.append([m-p, -p])

x.sort(reverse=True)
y.sort(reverse=True)
r = 0
for s, t in x:
    if r+s < 0:
        print("No")
        sys.exit()
    r += t
result = 0
for s, t in y:
    if result+s < 0:
        print("No")
        sys.exit()
    result += t
if r-result == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def f(s):
  m=0
  n=0
  for i in s:
    if i==")":n-=1
    else:n+=1
    m=min(m,n)
  return [m,n]
n=int(input())
s=[input()for _ in range(n)]
mab=[]
pab=[]
for i in range(n):
  ab=f(s[i])
  if sum(ab)>0:pab.append(ab)
  else:mab.append(ab)
pab.sort(reverse=1)
mab.sort(key=lambda x:x[0]-x[1])
#print(pab)
#print(mab)
ab=pab+mab
n=0
for a,b in ab:
  if n+a<0:exit(print("No"))
  n+=b
  if n<0:exit(print("No"))
if n==0:print('Yes')
else:print('No')

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import matplotlib.pyplot as plt
# from matplotlib.image import imread
def init():
    global N, Sp, Sm
    N = int(input())
    Sp = []
    Sm = []
    for i in range(N):
      l = input()
      u = 0
      h = 0
      for j in range(len(l)):
        if l[j] == '(':
          h += 1
        else:
          h -= 1
        if h < u:
          u = h
      if h >= 0:
        Sp.append([u, h])
      else:
        Sm.append([u-h, -h])
    Sp.sort(reverse=True)
    Sm.sort(reverse=True)

def main():
  init()
  p = check(Sp)
  m = check(Sm)
  if p != -1 and m != -1 and p ==m:
    print('Yes')
  else:
    print('No')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
plus_bracket = []
minus_bracket = []
zero_bracket = 0
for _ in range(n):
  mini = 0
  cur = 0
  for bracket in input():
    if bracket == '(':
      cur += 1
    else:
      cur -= 1
    if cur < mini:
      mini = cur
  if cur > 0:
    plus_bracket.append([mini, cur])
  elif cur < 0:
    minus_bracket.append([mini - cur, -cur])
  elif mini < zero_bracket:
    zero_bracket = mini

success = True
cur = 0
plus_bracket.sort(reverse=True)
minus_bracket.sort(reverse=True)
for bracket in plus_bracket:
  if cur + bracket[0] < 0:
    success = False
    break
  cur += bracket[1]
if cur + zero_bracket < 0:
  success = False
back_cur = 0
for bracket in minus_bracket:
  if back_cur + bracket[0] < 0:
    success = False
    break
  back_cur += bracket[1]
if cur != back_cur:
  success = False

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

Submission status: Time Limit Exceeded

Solution code:
import sqlite3

conn = sqlite3.connect(":memory:", isolation_level=None, check_same_thread=False)
conn.executescript(
    "CREATE TABLE t (max_o INTEGER, max_c INTEGER); CREATE INDEX ind1 ON t(max_o); CREATE INDEX ind2 ON t(max_c);",
)

N = int(input())
Ss = []
for _ in range(N):
    S = input()
    max_c = 0
    tot_o = 0
    tot_c = 0
    for c in S:
        if c == "(":
            tot_o += 1
        else:
            tot_c += 1
            max_c = max(max_c, tot_c - tot_o)
    Ss.append((tot_o - tot_c + max_c, max_c))
conn.executemany("INSERT INTO t VALUES (?, ?)", Ss)
d = 0
for max_o, max_c in conn.execute("SELECT * FROM t WHERE max_o >= max_c ORDER BY max_c"):
    if max_c > d:
        d = -1
        break
    d += max_o - max_c
for max_o, max_c in conn.execute(
    "SELECT * FROM t WHERE max_o < max_c ORDER BY max_o DESC"
):
    if max_c > d:
        d = -1
        break
    d += max_o - max_c
if d == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x[1:-1].count('(')
    r = len(x[1:-1]) - l
    if l != r: return 0

    return 1

def main():
    from itertools import permutations
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))
    comb_s = tuple(set(permutations(s)))

    res = tuple(filter(lambda x: checker(''.join(x)) == 1, comb_s))
    if not res:
        print('No')
    else:
        print('Yes')
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x[1:-1].count('(')
    r = len(x[1:-1]) - l
    if l != r: return 0

    return 1

def main():
    readline = sys.stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for i in range(n))
    comb_s = tuple(set(permutations(s)))

    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(')
    r = x.count(')')
    if l != r: return 0

    return 1

def main():
    readline = sys.stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for i in range(n))
    comb_s = tuple(set(permutations(s)))

    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

memo1 = []
memo2 = []
for i in range(N):
  S = input()
  sum_n = min_n = 0
  for s in S:
    if s == ')':
      sum_n -= 1
      min_n = min(min_n, sum_n)
    else:
      sum_n += 1
  if sum_n >= 0:
    memo1.append([min_n, sum_n])
  else:
    memo2.append([min_n-sum_n, -sum_n])

memo1.sort(reverse=True)
left = 0
for min_n, sum_n in memo1:
  if left + min_n < 0:
    print('No')
    quit()
  else:
    left += sum_n

memo2.sort(reverse=True)
right = 0
for min_n, sum_n in memo2:
  if right + min_n < 0:
    print('No')
    quit()
  else:
    right += sum_n

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(')
    r = x.count(')')
    if l != r: return 0

    return 1

def main():
    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    readline = sys.stdin.readline

    n = int(readline())
    s = (readline().strip() for i in range(n))

    comb_s = list(permutations(s))
    comb_s = tuple(set(comb_s))

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    l = x.count('(')
    r = x.count(')')
    if l != r: return 0

    return 1

def main():
    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

if __name__ == '__main__':
    readline = sys.stdin.readline

    n = int(readline())
    s = [readline().strip() for i in range(n)]

    comb_s = list(permutations(s))

    main()