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:
def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

S = [0]*N
A = [0]*N
B = [0]*N

for i in range(N):
    S[i] = input()
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == ')':
            a += 1
        else:
            a -= 1
        A[i] = max(A[i],a)

        if S[i][-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

#print('L',L)
SS = ""

for x in L:
    SS += S[x]

#print('SS',SS)
SA = 0
SB = 0
a = 0
b = 0
for j in range(len(SS)):
    if SS[j] == ')':
        a += 1
    else:
        a -= 1
    
    if SS[-j-1] == '(':
        b += 1
    else:
        b -= 1
    #print(j,a,b)
    SA = max(SA,a)
    SB = max(SB,b)

#print(SA,SB)
if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d=[]
e=[]
for i in range(n):
    p=[0,0]
    s=input()
    for j in s:
        if j==")":
            if p[0]!=0:
                p[0]-=1
            else:
                p[1]+=1
        else:
            p[0]+=1
    if p[0]-p[1]>=0:
        d.append(p)
    else:
        e.append(p)
d=sorted(d,key=lambda x:x[1])
e=sorted(e,key=lambda x:-x[0])
s=d+e
q=0
for i,j in s:
    if q<j:
        print("No")
        exit()
    else:
        q=q-j+i
if q==0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = 0
    max_L = 0
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


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


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    cnt = 0
    min_cnt = float("inf")
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            cnt += 1
        else:  # brackets[i] == ")"
            cnt -= 1
            min_cnt = min(min_cnt, cnt)
    
    return cnt, min_cnt

#-----
tmp_cnt_plus  = []
tmp_cnt_minus = []

for S in S_list:
    cnt, min_cnt = count_brackets(S)
    
    if cnt >= 0:
        tmp_cnt_plus.append( (cnt, min_cnt) )
    else:  # cnt < 0
        tmp_cnt_minus.append( (cnt, min_cnt) )


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


sum_bracket = 0
flag = True

for cnt, min_cnt in (tmp_cnt_plus + tmp_cnt_minus):
    if (sum_bracket + min_cnt) < 0:
        flag = False
        break
    
    sum_bracket += cnt


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


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


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R

#-----
cnt_brackets = []

for S in S_list:
    cnt_brackets.append( count_brackets(S) )


tmp_cnt1 = []
tmp_cnt2 = []

for cnt_L,cnt_R in cnt_brackets:
    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )

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


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R

#-----
cnt_brackets = []

for S in S_list:
    cnt_brackets.append( count_brackets(S) )


tmp_cnt1 = []
tmp_cnt2 = []

for cnt_L,cnt_R in cnt_brackets:
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )

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


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append((mim, end))
  else:
    S_n.append((end-mim, end))
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
for i in range(n):
  A.append(input())
  
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[]
for i in range(n):
  A.append(input())
  
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    min_tmp=0 #)))の
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            min_tmp=min(min_tmp,tmp)
    tmp=0
    max_tmp=0 #(((の
    for i in range(len(S)):
        i=len(S)-i-1
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp>0:
            max_tmp=max(max_tmp,tmp)
    if tmp>=0:
        plus.append((tmp,max_tmp,-min_tmp))
    else:
        minus.append((tmp,max_tmp,-min_tmp))

plus.sort(key=lambda x:x[2])
minus.sort(reverse=True,key=lambda x:x[1])
ans=0
for i,j,k in plus:
    if ans<k:
        print("No")
        exit()
    ans+=i
for i,j,k in minus:
    if ans<k:
        print("No")
        exit()
    ans+=i
if ans==0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S_ab=[]
S_ba=[]
for i in range(N):
    s=input()
    a=0
    b=0
    pre=0
    for j in range(len(s)):
        if s[j]==')':
            if pre==0:
                a+=1
            else:
                pre-=1
        elif s[j]=='(':
            pre+=1
    pre=0
    for j in range(len(s)-1,-1,-1):
        if s[j]=='(':
            if pre==0:
                b+=1
            else:
                pre-=1
        elif s[j]==')':
            pre+=1
    #print(a,b,s)
    if a<=b:
        S_ab.append((a,b))
    elif a>b:
        S_ba.append((a,b))
S_ab.sort(key=lambda x:x[0])
S_ba.sort(key=lambda x:x[1],reverse=True)
S=S_ab+S_ba
total_a=0
total_b=0
can=1
for j in range(N):
    a,b=S[j]
    total_a+=a
    if total_a>total_b:
        can=0
        break
    total_b+=b
if b>0 or total_a!=total_b:
    can=0
if can:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
if N==0:
    print("Yes")
    exit()

P=[]
M=[]
for i in range(N):
    s=input()
    f=0
    m=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if cnt<m:
                m=cnt
    if cnt>=0:
        P.append([m,cnt])
    else:
        M.append([m-cnt,-cnt])
P.sort(reverse=True)
M.sort(reverse=True)
#print(P)
#print(M)
SUM=0
for i,j in P:
    SUM+=j
for i,j in M:
    SUM-=j
if SUM!=0:
    print("No")
    exit()

SUMP=0
for i,j in P:
    if SUMP>=(-i):
        SUMP+=j
    else:
        print("No")
        exit()
        
SUMM=0
for i,j in M:
    if SUMM>=(-i):
        SUMM+=j
    else:
        print("No")
        exit()
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = a_count
    bi = b_count
    if bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

first_list= sorted(first_list, key=lambda s: s[1])
last_list= sorted(last_list, key=lambda s: s[1], reverse=True)

ans = ""
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]

a_count = 0
b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

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

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            st.pop()
    return st.count(')'), st.count('(')

cb_obs = list(map(count_cb_ob, S))
f = list(filter(lambda cb_ob: cb_ob[0] < cb_ob[1] , cb_obs))
b = list(filter(lambda cb_ob: cb_ob[0] > cb_ob[1] , cb_obs))
s = list(filter(lambda cb_ob: cb_ob[0] == cb_ob[1] , cb_obs))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    print('No')
else:
    print(ans)

Submission status: Time Limit Exceeded

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

def count_cb_ob(s):
    st = []
    for i, si in enumerate(s):
        if si == '(' or len(st) == 0 or st[-1] != '(':
            st.append(si)
        else:
            del st[-1]
    return st.count(')'), st.count('(')

cb_obs = list(map(count_cb_ob, S))
f = list(filter(lambda cb_ob: cb_ob[0] < cb_ob[1] , cb_obs))
b = list(filter(lambda cb_ob: cb_ob[0] > cb_ob[1] , cb_obs))
s = list(filter(lambda cb_ob: cb_ob[0] == cb_ob[1] , cb_obs))

f = sorted(f)
b = sorted(b, key=lambda x:x[1], reverse=True)

count = 0
ans = 'Yes'
for down, up in (*f, *s, *b):
    count -= down
    if count < 0:
        ans = 'No'
    count += up

if count != 0:
    print('No')
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
XR=[]
XL=[]
import heapq
for i in range(N):
  S=input()
  x=0
  R=0#)
  L=0
  for s in S:
    if s=='(':
      if x>=0:
        x+=1
      else:
        R+=-x
        x=1
    else:
      x-=1
  if x>0:
    L=x
  else:
    R+=-x
  if R==L==0:
    continue
  else:
    if R<=L:
      heapq.heappush(XL,[R,L])
    else:
      heapq.heappush(XR,[-L,R])
n=0
while len(XL)>0:
  x=heapq.heappop(XL)
  n-=x[0]
  if n<0:
    print('No')
    exit(0)
  n+=x[1]
while len(XR)>0:
  l,r=heapq.heappop(XR)
  x=[r,-l]
  n-=x[0]
  if n<0:
    print('No')
    exit(0)
  n+=x[1]
if n==0:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
XR=[]
XL=[]
for i in range(N):
  S=input()
  x=0
  R=0#)
  L=0
  for s in S:
    if s=='(':
      if x>=0:
        x+=1
      else:
        R+=-x
        x=1
    else:
      x-=1
  if x>0:
    L=x
  else:
    R+=-x
  if R==L==0:
    continue
  else:
    if R<=L:
      XL.append([R,L])
    else:
      XR.append([R,L])
XL=sorted(XL,key=lambda x:x[0])
XR=sorted(XR,key=lambda x:x[1])[::-1]
n=0
for x in XL+XR:
  n-=x[0]
  if n<0:
    print('No')
    exit(0)
  n+=x[1]
if n==0:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
XR=[]
XL=[]
for i in range(N):
  S=input()
  x=0
  R=0#)
  L=0
  for s in S:
    if s=='(':
      if x>=0:
        x+=1
      else:
        R+=-x
        x=1
    else:
      x-=1
  if x>0:
    L=x
  else:
    R+=-x
  if x==R==L==0:
    continue
  else:
    if R<=L:
      XL.append([R,L])
    else:
      XR.append([R,L])
XL=sorted(XL,key=lambda x:x[0])
XR=sorted(XR,key=lambda x:x[1])[::-1]
n=0
for x in XL+XR:
  n-=x[0]
  if n<0:
    print('No')
    exit(0)
  n+=x[1]
if n==0:
  print('Yes')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

for pos, neg in suff:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


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

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

for pos, neg in suff:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


def comp1(x, y):
	return x[1] - y[1]


def comp2(x, y):
	return -x[0] + y[0]


pref.sort( key=cmp_to_key(comp1))
suff.sort( key=cmp_to_key(comp2))

# pref.sort(key=lambda x: x[1])
# suff.sort(key=lambda x: -x[0])

pref += suff

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])

# def comp1(x, y):
# 	return x[1] - y[1]
#
#
# def comp2(x, y):
# 	return -x[0] + y[0]


# pref.sort( key=cmp_to_key(comp1))
# suff.sort( key=cmp_to_key(comp2))

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


totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

for pos, neg in suff:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])

# def comp1(x, y):
# 	return x[1] - y[1]
#
#
# def comp2(x, y):
# 	return -x[0] + y[0]


# pref.sort( key=cmp_to_key(comp1))
# suff.sort( key=cmp_to_key(comp2))

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


pref = pref + suff

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr1=[]
arr2=[]
for _ in range(n):
  s=input()
  cnt1=0
  cnt2=0
  for i in range(len(s)):
    if s[i]=='(':
      cnt1+=1
    else:
      if cnt1==0:
        cnt2+=1
      else:
        cnt1-=1
  if cnt1-cnt2>=0:
    arr1.append([cnt1,cnt2])
  else:
    arr2.append([cnt1,cnt2])
arr1=sorted(arr1,key=lambda x:x[1])
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
arr=arr1+arr2
cnt=0
for a,b in arr:
  if b>cnt:
    print('No')
    break
  else:
    cnt+=a-b
else:
  if cnt==0:
    print('Yes')
  else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
# 折れ線グラフで考えると
# ( : +1
# ) : -1
# 0で終わる
# 0未満にならない → 各文字列で最下点と和を利用
# 和がマイナスの部分と分けて、マイナス部分は反転して考える

n = int(input())
plus = []
minus = []
for i in range(n):
    min_v = 0
    sum_v = 0
    s = input()
    for j in range(len(s)):
        sum_v += 1 if s[j] == '(' else -1
        min_v = min(min_v, sum_v)
    if sum_v > 0:
        plus.append([min_v, sum_v])
    else:
        minus.append([min_v-sum_v, -sum_v])

plus.sort(key=lambda x:x[0], reverse=True)
minus.sort(key=lambda x:x[0], reverse=True)

sum_plus = 0
for min_v, sum_v in plus:
    if sum_plus + min_v < 0:
        print("No")
        exit()
    sum_plus += sum_v

sum_minus = 0
for min_v, sum_v in minus:
    if sum_minus + min_v < 0:
        print("No")
        exit()
    sum_minus += sum_v

if sum_plus == sum_minus:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n=int(input())
s=[input().strip("\n") for _ in range(n)]
p=[];m=[]
for si in s:
    cnt=0;a=0;b=0
    for i in range(len(si)):
        if si[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(si)-1,-1,-1):
        if si[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,si))
    else:
        m.append((-b,si))
p.sort();m.sort()
ss=""

for _,si in p:
    ss+=si
for _,si in m:
    ss+=si
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
##解説参照
##b,b-aを判定に使うことが困難
n=int(input())
p=[];m=[]
for _ in range(n):
    s=input()
    cnt=0;a=0;b=0
    for i in range(len(s)):
        if s[i]==")":
            cnt+=1
        else:
            cnt-=1
        a=max(a,cnt)
    cnt=0
    for i in range(len(s)-1,-1,-1):
        if s[i]=="(":
            cnt+=1
        else:
            cnt-=1
        b=max(b,cnt)
    if b-a>=0:
        p.append((a,s))
    else:
        m.append((-b,s))
p.sort();m.sort()
ss=""

for _,s in p:
    ss+=s
for _,s in m:
    ss+=s
cnt=0
for i in range(len(ss)):
    if ss[i]=="(":
        cnt+=1
    else:
        cnt-=1
    if cnt<0:
        print("No")
        exit()
if cnt:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #ここにコード
    #input
    from collections import Counter
    import itertools
    N = int(input())

    dp = [[0, 0] for _ in range(N)]
    for i in range(N):
        S = str(input())
        T = []
        for s in S:
            if s == "(":
                T.append(1)
            else:
                T.append(-1)
        x = list(itertools.accumulate(T))[-1]
        y = min(itertools.accumulate(T))
        dp[i] = [x, y]


    #output
    dp1 = [[x, y] for x, y in dp if x >= 0]
    dp2 = [[x, y] for x, y in dp if x < 0]
    dp1 = sorted(dp1, key = lambda x:x[1], reverse = True)
    dp2 = sorted(dp2, key = lambda x:x[0]-x[1], reverse = True)
    dp = dp1 + dp2

    checker = 0
    for p in dp:
        if checker + p[1] < 0:
            print("No")
            exit()
        checker += p[0]

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

LR = []
for s in S:
    left, right = 0, 0
    for ss in s:
        if ss == "(":
            left += 1
        else:
            if left:
                left -= 1
            else:
                right += 1
    LR.append([left, right])
#print(LR)

plus = []
minus = []
for l, r in LR:
    if l >= r:
        plus.append([l, r])
    else:
        minus.append([l, r])
        
plus.sort(key = lambda x: x[1])
minus.sort(key = lambda x: -x[0])

cnt = 0
for l, r in plus + minus:
    cnt -= r
    if cnt < 0:
        print("No")
        exit()
    cnt += l
        
if cnt == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

def main():
    N = int(input())
    S = list(input().strip() for _ in range(N))
    print(solve(S))

def get_count(s):
    result = [0, 0]
    cum_sum = 0
    for c in s:
        if c == ')':
            cum_sum -= 1
        else:
            cum_sum += 1
        result[0] = max(result[0], -cum_sum)
    result[1] = result[0] + cum_sum
    return result

# Made-up name, don't remember what to call this. Radix-ish
def silly_sort(array, value_min, value_max, get_value):
    if len(array) == 0:
        return
    cache = [None for _ in range(value_max - value_min + 1)]
    for elem in array:
        # Assume elem[0] is the value
        value = get_value(elem) - value_min
        if cache[value] is None:
            cache[value] = []
        cache[value].append(elem)
    for values in cache:
        if values is None:
            continue
        for value in values:
            yield value

def solve(S):
    counts = list(map(get_count, S))
    first_group = []
    second_group = []
    min_first_group = float('inf')
    max_first_group = 0
    min_second_group = float('inf')
    max_second_group = 0

    for c in counts:
        if c[0] - c[1] <= 0:
            first_group.append(c)
            max_first_group = max(max_first_group, c[0])
            min_first_group = min(min_first_group, c[0])
        else:
            second_group.append(c)
            max_second_group = max(max_second_group, c[1])
            min_second_group = min(min_first_group, c[1])
    first_group = silly_sort(first_group, min_first_group, max_first_group, lambda c: c[0])
    second_group = reversed(list(silly_sort(second_group, min_second_group, max_second_group, lambda c: c[1])))

    order = chain(first_group, second_group)


    cum_sum = 0
    for c in order:
        cum_sum -= c[0]
        if cum_sum < 0:
            return 'No'
        cum_sum += c[1]
    if cum_sum == 0:
        return 'Yes'
    return 'No'

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input().strip() for _ in range(N))
    print(solve(S))

def get_count(s):
    result = [0, 0]
    cum_sum = 0
    for c in s:
        if c == ')':
            cum_sum -= 1
        else:
            cum_sum += 1
        result[0] = max(result[0], -cum_sum)
    result[1] = result[0] + cum_sum
    return result

def solve(S):
    counts = list(map(get_count, S))
    first_groups = sorted(filter(lambda c: c[0] - c[1] <= 0, counts), key=lambda c: c[0])
    second_groups = sorted(filter(lambda c: c[0] - c[1] > 0, counts), key=lambda c: -c[1])
    order = first_groups + second_groups

    cum_sum = 0
    for c in order:
        cum_sum -= c[0]
        if cum_sum < 0:
            return 'No'
        cum_sum += c[1]
    if cum_sum == 0:
        return 'Yes'
    return 'No'

if __name__ == '__main__':
    main()