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())
slist = []
for i in range(n):
    slist.append(input())

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

    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
            min_s += ")"
    min_s += "("*b_count

    ai = len(min_s)-b_count
    bi = b_count

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

sorted(first_list, key=lambda s: s[1])
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]

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
        min_s += ")"
min_s += "("*b_count

if min_s == "":
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

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]

    remove_bracket =s.replace("()","")
    while remove_bracket != s:
        s = remove_bracket
        remove_bracket =s.replace("()","")
    
    ai = s.count(")")
    bi = s.count("(")
    if bi-ai >= 0:
        first_list.append([s,ai])
    else:
        last_list.append([s,bi])

sorted(first_list, key=lambda s: s[1])
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]

remove_bracket = ans.replace("()","")
while remove_bracket != ans:
    ans = remove_bracket
    remove_bracket =ans.replace("()","")

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

Submission status: Wrong Answer

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n = 4
    S = ['((()))', '((((((', '))))))', '()()()']

  else:
    ## INPUT 
    n = int(input())
    #a, b = map(int, input().split())
    S = [input() for _ in range(n)]

  ## SUBMITION CODES HERE
  def CNT(A):
    tmp, Min = 0, 0
    for a in A:
        if a == '(': tmp += 1
        else: -1
        Min = min(Min, tmp)
    return (-Min, tmp-Min)
  
  T = [CNT(s) for s in S]

  pls = []
  mis = []
  for l, r in T:
    if l <= r: pls.append((l, r))
    else: mis.append((l, r))

  pls.sort(key=lambda a: a[0])
  mis.sort(key=lambda a: a[1], reverse=True)
  total = pls + mis

  levl = 0
  for l, r in total:
    levl -= l
    if levl < 0:
        print('No')
        exit()
    levl += r

  print('Yes' if levl == 0 else 'No')
    
main()

Submission status: Wrong Answer

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n = 4
    S= ['((()))', '((((((', '))))))', '()()()']

  else:
    ##INPUT 
    n = int(input())
    #a, b = map(int, input().split())
    S = [input() for _ in range(n)]

  ## SUBMITION CODES HERE
  def CNT(A):
    tmp, Min = 0, 0
    for a in A:
        if a == '(': tmp += 1
        else: -1
        Min = min(Min, tmp)
    return (-Min, tmp-Min)
  
  T = [CNT(s) for s in S]

  pls = []
  mis = []
  for l, r in T:
    if l <= r: pls.append((l, r))
    else: mis.append((l, r))

  pls.sort(key=lambda a: a[0])
  mis.sort(key=lambda a: a[1], reverse=True)
  total = pls + mis

  levl = 0
  for l, r in total:
    levl -= l
    if levl < 0:
        print('No')
        exit()
    levl += r

  print('Yes' if levl == 0 else 'No')
    
main()

Submission status: Wrong Answer

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
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
count=0
for i in range(n):
  s.append(input())
  for el in s:
    if el=="(":
            count+=1
    else:
            count-=1
if not count:
  print("Yes")
else:print("No")

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
count=0
for i in range(n):
  s.append(input())
  for el in s:
    if el=="(":
            count+=1
    elif el==")":
            count-=1
if not count:
  print("Yes")
else:print("No")

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
for i in range(n):
  s.append(input())
for i in range(10**3):
  count=0
  for j in range(min(10**3,n)):
    b=random.randrange(0,max(len(s[j])-99,1))
    for k in range(b,min(len(s[j]),100+b)):
      if s[j][k]=="(":
              count+=1
      elif s[j][k]==")":
              count-=1
      else:raise Exception
  try:
    dic[count]+=1
  except:
    dic[count]=1
#print(dic)
try:
  if dic[0]>10:
    print("Yes")
  else:
    print("No")
except:print("No")

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
for i in range(n):
  s.append(input())
for i in range(5*10**2):
  count=0
  for j in range(min(10**3,n)):
    b=random.randrange(0,max(len(s[j])-99,1))
    for k in range(b,min(len(s[j]),100+b)):
      if s[j][k]=="(":
              count+=1
      elif s[j][k]==")":
              count-=1
      else:raise Exception
  try:
    dic[count]+=1
  except:
    dic[count]=1
#print(dic)
try:
  if dic[0]>10:
    print("Yes")
  else:
    print("No")
except:print("No")

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
for i in range(n):
  s.append(input())
for i in range(10**2):
  count=0
  for j in range(min(10**3,n)):
    b=random.randrange(0,max(len(s[j])-99,1))
    for k in range(b,min(len(s[j]),100+b)):
      if s[j][k]=="(":
              count+=1
      elif s[j][k]==")":
              count-=1
      else:raise Exception
  try:
    dic[count]+=1
  except:
    dic[count]=1
#print(dic)
try:
  if dic[0]>5:
    print("Yes")
  else:
    print("No")
except:print("No")

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import random
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
dic={}
n=read()
s=[]
for i in range(n):
  s.append(input())
for i in range(10**2):
  count=0
  for j in range(min(10**3,n)):
    b=random.randrange(0,max(len(s[j])-99,1))
    for k in range(b,min(len(s[j]),100+b)):
      if s[j][k]=="(":
              count+=1
      elif s[j][k]==")":
              count-=1
      else:raise Exception
  try:
    dic[count]+=1
  except:
    dic[count]=1
print(dic)
try:
  if dic[0]>5:
    print("Yes")
  else:
    print("No")
except:print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
jsum=0
gjlist=[]
ejlist=[]
esum=0

def jouka(t):
	global jsum
	global gjlist
	global ejlist
	global esum
	
	tmpj=0
	tmpe=0
	
	for i in range(len(t)):
		if t[i] == "(":
			tmpj += 1
		else:
			if tmpj == 0:
				tmpe +=1
			else:
				tmpj -=1
		
	if tmpe == 0:
		jsum += tmpj
	elif tmpj == 0:
		esum += tmpe
	elif tmpj > tmpe:
		gjlist.append([tmpe,tmpj])
	else:
		ejlist.append([tmpe,tmpj])

for j in range(n):
	jouka(input())

gjlist.sort(key=lambda x:x[0])
ejlist.sort(reverse = True,key=lambda x:x[0])

streak=jsum
for gj in gjlist:
	if gj[0] > streak:
		print("No")
		sys.exit()
	else:
		streak += gj[1]-gj[0]

for ej in ejlist:
	if ej[0] > streak:
		print("No")
		sys.exit()
	else:
		streak += gj[1]-gj[0]

if streak == esum:
	print("Yes")
else:
	print("No")

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
def f(X):
  R=[0]
  for x in X:
    if x==")":
      R.append(R[-1]+1)
    else:
      R.append(R[-1]-1)
  res1=max(R)
  R=[0]
  for x in X[::-1]:
    if x=="(":
      R.append(R[-1]+1)
    else:
      R.append(R[-1]-1)
  res2=max(R)
  return (res1,res2)

A=[0,0]
for _ in range(n):
  a,b=A
  c,d=f(input())
  if min(b,c)<=min(a,d):
    if d>=a:
      A=[c,d-a+b]
    else:
      A=[c+a-d,b]
  else:
    if b>=c:
      A=[a,b-c+d]
    else:
      A=[a+c-b,d]
if A==[0,0]:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
def f(X):
  R=[0]
  for x in X:
    if x==")":
      R.append(R[-1]+1)
    else:
      R.append(R[-1]-1)
  res1=max(R)
  R=[0]
  for x in X[::-1]:
    if x=="(":
      R.append(R[-1]+1)
    else:
      R.append(R[-1]-1)
  res2=max(R)
  return (res1,res2)

A=[0,0]
for _ in range(n):
  a,b=A
  c,d=f(input())
  if min(b,c)<=min(a,d):
    if d>=a:
      A=[c,d-a+b]
    else:
      A=[c+a-d,b]
  else:
    if b>=c:
      A=[a+b-c,d]
    else:
      A=[a,c-b+d]
if A==[0,0]:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

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

s = 0
L, R = 0, 0 
l, r = [], []
for i in range(N):
    left, right = 0, 0
    m, M = 0, 0
    for u in S[i]:
        if u == "(":
            left += 1
        else:
            right += 1
        M = max(M, left - right)
        m = max(m, right - left)
    
    sss = left - right
    if sss > 0 and m == 0:
        L += M
    elif sss < 0 and M == 0:
        R += m
    else:
        if left >= right:
            l.append([m, - left + right])
        else:
            r.append([M, - right + left])
            
    s += left - right

if s == 0:
    judge = 0
    for u, v in l:
        v *= -1
        if L >= u:
            L += v
        else:
            judge = 10
    
    for u, v in r:
        v *= -1
        if R >= u:
            R += v
        else:
            judge = 10
    
    if judge == 0:
        print("Yes")
    else:
        print("No")
        
else:
    print("No")

Submission status: Wrong Answer

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

s = 0
L, R = 0, 0 
l, r = [], []
for i in range(N):
    left, right = 0, 0
    m, M = 0, 0
    for u in S[i]:
        if u == "(":
            left += 1
        else:
            right += 1
        M = max(M, left - right)
        m = max(m, right - left)
    
    sss = left - right
    if sss > 0 and m == 0:
        L += M
    elif sss < 0 and M == 0:
        R += m
    else:
        if left >= right:
            l.append([m, left - right])
        else:
            r.append([M, right - left])
            
    s += left - right

if s == 0:
    judge = 0
    for u, v in l:
        if L >= u:
            L += v
        else:
            judge = 10
    
    for u, v in r:
        if R >= u:
            R += v
        else:
            judge = 10
    
    if judge == 0:
        print("Yes")
    else:
        print("No")
        
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = [readline().rstrip().decode() for _ in range(n)]
inc = []
dec = []
for ss in s:
    d, r = 0, 0
    for m in ss:
        d += (1 if s == '(' else -1)
        r = max(r, -d)
    (dec if d < 0 else inc).append((d, r))
inc.sort(key=lambda x: x[1])
dec.sort(key=lambda x: x[0] + x[1])
p1 = 0
p2 = 0
flag = True
for i in inc:
    flag &= i[1] <= p1
    p1 += i[0]
for d in dec:
    flag &= p2 >= d[0] + d[1]
    p2 -= d[0]
print('Yes' if flag and p1 == p2 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = [readline().rstrip().decode() for _ in range(n)]
inc = []
dec = []
for ss in s:
    d, r = 0, 0
    for m in ss:
        d += 1 if s == '(' else -1
        r = max(r, -d)
    (dec if d < 0 else inc).append((d, r))
inc.sort(key=lambda x: x[1])
dec.sort(key=lambda x: x[0] + x[1])
p1 = 0
p2 = 0
flag = True
for i in inc:
    flag &= i[1] <= p1
    p1 += i[0]
for d in dec:
    flag &= p2 >= d[0] + d[1]
    p2 -= d[0]
print('Yes' if flag and p1 == p2 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
memo = [[0, 0] for _ in range(n)]
for i in range(n):
    s = readline().rstrip().decode()
    flag = False
    for m in s:
        if m == '(':
            memo[i][0] += 1
            flag = True
        else:
            if flag:
                memo[i][0] -= 1
                if memo[i][0] == 0:
                    flag = False
            else:
                memo[i][1] += 1
memo.sort(key=lambda x: (x[1], -x[0]))
if memo[0][1] != 0 or memo[-1][0] != 0:
    print('No')
else:
    check = 0
    for bf, af in memo:
        check -= af
        if check < 0:
            print('No')
            exit()
        check += bf
    print('Yes' if check == 0 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = [readline().rstrip().decode() for _ in range(n)]
memo = [[0, 0] for _ in range(n)]
for i, ss in enumerate(s):
    flag = False
    for m in ss:
        if m == '(':
            memo[i][0] += 1
            flag = True
        else:
            if flag:
                memo[i][0] -= 1
                if memo[i][0] == 0:
                    flag = False
            else:
                memo[i][1] += 1
memo.sort(key=lambda x: (x[1], -x[0]))
if memo[0][1] != 0:
    print('No')
else:
    check = 0
    for bf, af in memo:
        check -= af
        if check < 0:
            print('No')
            exit()
        check += bf
    print('Yes' if check == 0 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = [readline().rstrip().decode() for _ in range(n)]
memo = [[0, 0] for _ in range(n)]
for i, ss in enumerate(s):
    flag = False
    for m in ss:
        if m == '(':
            memo[i][0] += 1
            flag = True
        else:
            if flag:
                memo[i][0] -= 1
                if memo[i][0] == 0:
                    flag = False
            else:
                memo[i][1] += 1
memo.sort(key=lambda x: x[1])
if memo[0][1] != 0:
    print('No')
else:
    check = 0
    for bf, af in memo:
        check -= af
        if check < 0:
            print('No')
            exit()
        check += bf
    print('Yes' if check == 0 else 'No')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()

LSTP=[]
LSTN=[]
for i in range(N):
    cnt = 0
    cntMin = 0
    s = input()
    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1
        cntMin = min(cntMin, cnt)
    # print(cntMin)
    if cnt >= 0:
        LSTP.append((cntMin, cnt))
    else:
        LSTN.append((-(cnt-cntMin), -cnt))

LSTP.sort(reverse=True)
LSTN.sort(reverse=True)

res = 0
for cntMin, cnt in LSTP:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

res2 = 0
for cntMin, cnt in LSTN:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res2 += cnt

if res - res2 == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()

LSTP=[]
LSTN=[]
for i in range(N):
    cnt = 0
    cntMin = 0
    s = input()
    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1
        cntMin = min(cntMin, cnt)
    # print(cntMin)
    if cnt >= 0:
        LSTP.append((cntMin, cnt))
    else:
        LSTN.append((cntMin, cnt))

LSTP.sort(reverse=True)
LSTN.sort()

res = 0
for cntMin, cnt in LSTP:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

for cntMin, cnt in LSTN:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()

LSTP=[]
LSTN=[]
for i in range(N):
    cnt = 0
    cntMin = 10000000000
    s = input()
    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1
        cntMin = min(cntMin, cnt)
    # print(cntMin)
    if cnt >= 0:
        LSTP.append((cntMin, cnt))
    else:
        LSTN.append((cntMin, cnt))

LSTP.sort(reverse=True)
LSTN.sort()

res = 0
for cntMin, cnt in LSTP:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

for cntMin, cnt in LSTN:
    if res + cntMin < 0:
        print("No")
        exit(0)
    res += cnt

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()

LSTP=[]
LSTN=[]
for i in range(N):
    cnt = 0
    cntMin = 0
    s = input()
    for c in s:
        if c == "(":
            cnt += 1
        else:
            cnt -= 1
        cntMin = min(cntMin, cnt)
    if cnt >= 0:
        LSTP.append((cntMin, cnt))
    else:
        LSTN.append((cntMin, cnt))

LSTP.sort(reverse=True)
LSTN.sort()

cur_min = 0
res = 0
for cntMin, cnt in LSTP:
    cur_min = res + cntMin
    res += cnt
    if cur_min < 0:
        print("No")
        exit(0)
for cntMin, cnt in LSTN:
    cur_min = res + cntMin
    res += cnt
    if cur_min < 0:
        print("No")
        exit(0)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def seq_positive(s):
        state = 0
        for l, st in s:
            if state+l < 0:
                return False
            state += st
        return True

    # 部分括弧列の特徴量を計算する。
    # 経過中の最小値と、最終到達値
    left_seq = []
    right_seq = []
    total = 0
    for s in S:
        state = 0
        lower = 0
        for c in s:
            if c == "(":
                state += 1
            else:
                state -= 1
            lower = min(lower, state)
        if state > 0:
            left_seq.append((lower, state))
        else:
            right_seq.append((min(0, lower-state), -state))
        total += state

    left_seq.sort()
    right_seq.sort()

    if seq_positive(left_seq) and seq_positive(right_seq) and total == 0:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def seq_positive(s):
        state = 0
        for l, st in s:
            if state+l < 0:
                return False
            state += st
        return True

    # 部分括弧列の特徴量を計算する。
    # 経過中の最小値と、最終到達値
    left_seq = []
    right_seq = []
    total = 0
    for s in S:
        state = 0
        lower = 0
        for c in s:
            if c == "(":
                state += 1
            else:
                state -= 1
            lower = min(lower, state)
        if state > 0:
            left_seq.append((lower, state))
        else:
            right_seq.append((lower-state, -state))
        total += state

    left_seq.sort()
    right_seq.sort()

    if seq_positive(left_seq) and seq_positive(right_seq) and total == 0:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if mb >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    front.sort(key=lambda x: x[0], reverse=True)
    back.sort(key=lambda x: x[0]-x[1], reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            # print("負", s)
            return
        m += mb
    if m == 0:
        yes()
    else:
        # print("非零到達")
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if ma >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    back.sort(key=lambda x: x[1] != x[0], reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            # print("負", s)
            return
        m += mb
    if m == 0:
        yes()
    else:
        # print("非零到達")
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb in T:
        if ma >= 0:
            front.append((ma, mb))
        else:
            back.append((ma, mb))

    back.sort(key=lambda x: (x[1], x[0]), reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb in front+back:
        if m + ma < 0:
            no()
            return
        m += mb
    if m == 0:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, S: "List[str]"):

    def f(s):
        ans = [0]*(len(s)+1)
        m = 0
        for i, c in enumerate(s):
            if c == "(":
                m += 1
            else:
                m -= 1
            ans[i] = m
        return min(*ans), m, s

    # 数値化(最小値, 到達値)
    T = [f(s) for s in S]

    front = []
    back = []
    for ma, mb, s in T:
        if ma >= 0:
            front.append((ma, mb, s))
        else:
            back.append((ma, mb, s))

    back.sort(key=lambda x: (x[1]-x[0], -x[0]), reverse=True)
    # print(front)
    # print(back)

    m = 0
    for ma, mb, s in front+back:
        if m + ma < 0:
            no()
            return
        m += mb
    if m == 0:
        yes()
    else:
        no()

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()