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: Accepted

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
for i in range(n):
    l.append(list(input()))

p=0
q=0
for i in range(n):
    for j in l[i]:
        if j=='(':
            p+=1
        else:
            q+=1
if p!=q:
    print('No')
    exit()
pl=[]
ql=[]
ml=[]
for i in range(n):
    a=l[i]
    p=0
    q=0
    for j in a:
        if j=='(':
            p+=1
        else:
            q+=1
    if p>q:
        pl.append(a)
    elif p<q:
        ql.append(a)
    else:
        ml.append(a)
if pl:
    pp=[]
    for i in pl:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b
if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    #d=0
    if not pl:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

if ql:
    pp=[]
    for i in ql:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    if not ql:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

print('Yes')

Submission status: Accepted

Solution code:
# F - Bracket Sequencing
import sys
readline = sys.stdin.readline

N = int(input())
L = []
R = []
for _ in range(N):
    S = readline().strip()
    sums = 0
    mins = 0
    for s in S:
        if s == '(':
            sums += 1
        else:
            sums -= 1
            mins = min(mins, sums)
    if sums >= 0:
        L.append((sums, mins))
    else:
        R.append((-sums, mins-sums))

L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

# 最終的な '(' - ')' の数
diff = [0]*N
for i in range(N):
    num = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            num += 1
        else:
            num -= 1
    diff[i] = num

if sum(diff) != 0:
    print('No')
    exit()

# 条件が最も厳しい場所での括弧の数の差
bottom = [0]*N
for i in range(N):
    if diff[i] >= 0:
        num = 1 if S[i][0] == ')' else -1
        val = num
        for j in range(1,len(S[i])):
            if S[i][j] == '(':
                num -= 1
            else:
                num += 1
                val = max(val,num)
        bottom[i] = val
    else:
        num = 1 if S[i][-1] == '(' else -1
        val = num
        for j in range(1,len(S[i]))[::-1]:
            if S[i][j] == ')':
                num -= 1
            else:
                num += 1
                val = max(val,num)
        bottom[i] = val
    
up = []
down = []
for i in range(N):
    if diff[i] >= 0:
        up.append((diff[i],bottom[i]))
    else:
        down.append((diff[i],bottom[i]))

up.sort(key=lambda x: x[1])
down.sort(key=lambda x: -x[1])

r = 0
for u in up:
    if r < u[1]:
        print('No')
        exit()
    else:
        r += u[0]

r = 0
for d in down[::-1]:
    if r < d[1]:
        print('No')
        exit()
    else:
        r += -d[0]

print('Yes')

Submission status: Accepted

Solution code:
#abc167_e

n = int(input())

pos = []
neg = []

for _ in range(n):
    s = input()
    low_pos = 0
    increase= 0
    for v in s:
        if v=="(":
            increase += 1
        else:
            increase -= 1
            low_pos = min(low_pos, increase)
    
    if increase >= 0:
        pos.append((low_pos, increase))
    else:
        #reverse left from right
        low_pos, increase =  low_pos - increase, -increase        
        neg.append((low_pos, increase))
    
pos.sort()
pos.reverse() #lowが高い順にする.
neg.sort()
neg.reverse() #lowが高い順にする.

now_pos = 0
for low_pos, increase in pos:
    if now_pos + low_pos < 0:
        print("No")  #impossible
        exit()
    else:
        now_pos += increase

right_pos = 0       
for low_pos, increase in neg:
    if right_pos + low_pos < 0:
        print("No")  #impossible
        exit()
    else:
        right_pos += increase

if right_pos != now_pos:
    print("No")
    exit()
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(readline())

ls = []
rs = []

total = 0
S = list(map(lambda x: x.strip().decode(), readlines()))

for i in range(n):
    s = S[i]

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0:
        OK = False

h = 0
for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:(x[1], x[0]), reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[1] - x[0], -x[0]))

    for i in range(len(ways_pos)):
        go, max_depth = ways_pos[i]
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

    for i in range(len(ways_neg)):
        go, max_depth = ways_neg[i]
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:(x[1], x[0]), reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[1] - x[0], -x[0]), reverse=True)[::-1]

    for i in range(len(ways_pos)):
        go, max_depth = ways_pos[i]
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

    for i in range(len(ways_neg)):
        go, max_depth = ways_neg[i]
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:(x[1], x[0]), reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[1] - x[0], -x[0]), reverse=True)[::-1]

    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None

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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[1], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1]), reverse=True)

    idx = list(range(len(ways_pos)))



    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            print("No")
            return None


    tmp =[]
    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None


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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  b=b*-1
  if b==0:
    c=c+a
  elif a>=0:
    B.append([b,-1*a])
  else:
    A.append([b+a,a])
A.sort()
B.sort()
f=0
for i in range(len(B)):
  if c-B[i][0]<0:
    f=1
  c=c-B[i][1]
d=0
for i in range(len(A)):
  if d-A[i][0]<0:
    f=1
  d=d-A[i][1]
if c!=d:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    SS = read().split()

    for S in SS:
        path = [0]
        for s in S:
            path.append(path[-1]+ dic[s])
        ways.append((path[-1], min(path)))

    ways_pos = sorted([(a,b) for a,b in ways if a >= 0], key = lambda x:x[0], reverse=True)
    ways_neg = sorted([(a,b) for a,b in ways if a < 0], key = lambda x:(x[0] - x[1]), reverse=True)

    tmp = []
    for go, max_depth in ways_pos:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None

    tmp =[]
    for go, max_depth in ways_neg:
        if current + max_depth >= 0:
            current += go
        else:
            tmp.append((go, max_depth))

    for go, max_depth in tmp:
        if current + max_depth >= 0:
            current += go
        else:
            print('No')
            return None


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

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
N = int(input())
G2,G4 = [],[]
cnt2 = 0
cnt3 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        cnt3 += cnt
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += cnt3

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	pazuru_nobori = []
	pazuru_kudari = []
	for i in range(N):
		S = inputStr()
		tmp = 0
		min_tmp = 0
		for s in S:
			if s == "(":
				tmp += 1
			else:
				tmp -= 1
			if min_tmp > tmp:
				min_tmp = tmp

		if tmp >= 0:
			pazuru_nobori.append((min_tmp,tmp))
		else:
			pazuru_kudari.append((min_tmp,tmp))

	pazuru_nobori.sort()
	pazuru_nobori = pazuru_nobori[::-1]

	score = 0
	for i,val in enumerate(pazuru_nobori):
		min_tmp,tmp = val
		if score + min_tmp < 0:
			print("No")
			sys.exit()
		score += tmp

	pazuru_kudari_non = []
	for i,val in enumerate(pazuru_kudari):
		min_tmp,tmp = val

		min_tmp_2 = min_tmp - tmp
		tmp_2 = -1 * tmp

		pazuru_kudari_non.append((min_tmp_2,tmp_2))

	pazuru_kudari_non.sort()
	pazuru_kudari_non = pazuru_kudari_non[::-1]

	score2 = 0
	for i,val in enumerate(pazuru_kudari_non):
		min_tmp,tmp = val
		if score2 + min_tmp < 0:
			print("No")
			sys.exit()
		score2 += tmp

	if score2 == score:
		print("Yes")
	else:
		print("No")





#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# N 個のボールを K グループに分ける場合のパターン数
def sunuke(N, K, mod=10**9+7):
	if N < K or K-1 < 0:
		return 0
	else:
		return combination(N-1, K-1, mod)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# dfs のサンプル
def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())

def checkNonnegative(brankets):
    curup = 0
    for (minup , up) in sorted(brankets , key= itemgetter(0) , reverse = True):
        if curup + minup < 0:
            return False
        curup += up
    return True

def canArrangeBranket(brankets):
    totup = 0
    left_brankets = []
    right_brankets = []
    for branket in brankets:
        up = 0
        minup = 0
        for c in list(branket):
            if c == '(':
                up += 1
            else:
                up -= 1
                minup = min(minup , up)
        totup += up
        if up >= 0:
            left_brankets.append((minup , up))
        else:
            right_brankets.append((minup - up , - up))
    if totup != 0:
        return False
    return checkNonnegative(left_brankets) and checkNonnegative(right_brankets)

branketList = []
for i in range(N):
    l = input()
    branketList.append(l)

if canArrangeBranket(branketList):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0: return False
        h += p[1]
    return True

N = int(input())
S = [input().strip() for i in range(N)]

total = 0
ps, ms = [], []
for s in S:
    h, b = 0, 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h > 0:
        ps.append([b, h])
    else:
        ms.append([b-h, -h])
    total += h

ps.sort(reverse=True)
ms.sort(reverse=True)
if check(ps) and check(ms) and total == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n = int(raw_input())
def gb(s):
	bal,m = 0,0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)
-1 -1 -1 -3 -5 -11 -23 

-23 -11 -5 -3 -1 -1 -1

rs = [gb(raw_input()) for _ in range(n)]
rs.sort(key = lambda x: (0, -x[1]) if x[0]>=0 else (1,x[1] - x[0], x[0]))

def f(rs):
	s = 0
	for aa,bb in rs:
		if s + bb < 0: return False
		s += aa
	return s == 0

print 'Yes' if f(rs) else 'No'

Submission status: Accepted

Solution code:
n = int(raw_input())
def gb(s):
	bal,m = 0,0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


rs = [gb(raw_input()) for _ in range(n)]
rs.sort(key = lambda x: (0,-x[1], x[0]) if x[0]>=0 else (1,x[1] - x[0], -x[0]))

def f(rs):
	s = 0
	for aa,bb in rs:
		if s + bb < 0: return False
		s += aa
	return s == 0

print 'Yes' if f(rs) else 'No'

Submission status: Accepted

Solution code:
n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


rs = [gb(raw_input()) for _ in range(n)]
rs.sort(key = lambda x: (0,-x[1], -x[0]) if x[0]>=0 else (1,x[1] - x[0], -x[0]))

def f(rs):
	s = 0
	for aa,bb in rs:
		if s + bb < 0: return False
		s += aa
	return s == 0

print 'Yes' if f(rs) else 'No'

Submission status: Accepted

Solution code:
n = int(raw_input())
def gb(s):
	bal = 0
	m = 0
	for l in s: 
		bal += 1 if l == '(' else -1
		m = min(m, bal)
	return (bal,m)


adds, dels = [], []
for _ in range(n):
	e = gb(raw_input())
	if e[0] >= 0:
		adds.append(e)
	else:
		dels.append(e)
adds.sort(key = lambda x: (-x[1], -x[0]))
dels.sort(key = lambda x: (x[1] - x[0], -x[0]))
def f(adds, dels):
	s = 0
	for aa,bb in adds:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
		

	for aa,bb in dels:

		if s + aa < 0:
			return False
		if s + bb < 0:
			return False
		s += aa
	return s == 0

print 'Yes' if f(adds, dels) else 'No'

Submission status: Accepted

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


def solve():
    N = int(input())
    brackets_generator = (readline().strip() for _ in range(N))

    grads_positive = list()
    grads_negative = list()

    total = 0
    for brackets in brackets_generator:

        elevation, bottom = 0, 0

        for bk in brackets:

            elevation += 1 if bk == '(' else -1
            bottom = min(bottom, elevation)

        if elevation >= 0:
            grads_positive.append((bottom, elevation))
        elif elevation < 0:
            grads_negative.append((bottom - elevation, -elevation))

        total += elevation

    if total != 0:
        return False

    grads_positive.sort(reverse=True)
    grads_negative.sort(reverse=True)

    def is_good(grads):
        elevation, bottom = 0, 0
        for grad in grads:
            bottom = elevation + grad[0]
            if bottom < 0:
                return False
            elevation += grad[1]

        return True

    return is_good(grads_positive) and is_good(grads_negative)


def main():
    ok = solve()
    if ok:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
input = lambda: sys.stdin.readline().rstrip()

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


def bracket(x):
    # f: final sum of brackets '(':+1, ')': -1
    # m: min value of f
    f = m = 0
    for i in range(len(x)):
        if x[i] == '(':
            f += 1
        else:
            f -= 1
        m = min(m, f)
    # m <= 0
    return f, m


l1 = []
l2 = []
for i in range(n):
    fi, mi = bracket(s[i])
    if fi >= 0:
        l1.append((fi, mi))
    else:
        l2.append((fi, mi))

l1.sort(key=lambda x: -x[1])
l2.sort(key=lambda x: -(x[0] - x[1]))
l = l1 + l2
v = 0
for fi, mi in l:
    if v + mi >= 0:
        v += fi
    else:
        v = -1
        break

ans = 'Yes' if v == 0 else 'No'
print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
input = lambda: sys.stdin.readline().rstrip()

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


def bracket(x):
    # f: final sum of brackets '(':+1, ')': -1
    # m: min value of f
    f = m = 0
    for i in range(len(x)):
        if x[i] == '(':
            f += 1
        else:
            f -= 1
        m = min(m, f)
    # m <= 0
    return f, m


def func(l):
    # l = [(f, m)]
    l.sort(key=lambda x: -x[1])
    v = 0
    for fi, mi in l:
        if v + mi >= 0:
            v += fi
        else:
            return -1
    return v


l1 = []
l2 = []
for i in range(n):
    fi, mi = bracket(s[i])
    if fi >= 0:
        l1.append((fi, mi))
    else:
        l2.append((-fi, mi - fi))

v1 = func(l1)
v2 = func(l2)
if v1 == -1 or v2 == -1:
    ans = 'No'
else:
    ans = 'Yes' if v1 == v2 else 'No'

print(ans)

Submission status: Accepted

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


def bracket(x):
    # f: final sum of brackets '(':+1, ')': -1
    # m: min value of f
    f = m = 0
    for i in range(len(x)):
        if x[i] == '(':
            f += 1
        else:
            f -= 1
        m = min(m, f)
    # m <= 0
    return f, m


def func(l):
    # l = [(f, m)]
    l.sort(key=lambda x: -x[1])
    v = 0
    for fi, mi in l:
        if v + mi >= 0:
            v += fi
        else:
            return -1
    return v


l1 = []
l2 = []
for i in range(n):
    fi, mi = bracket(s[i])
    if fi >= 0:
        l1.append((fi, mi))
    else:
        l2.append((-fi, mi - fi))

v1 = func(l1)
v2 = func(l2)
if v1 == -1 or v2 == -1:
    ans = 'No'
else:
    ans = 'Yes' if v1 == v2 else 'No'

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# (と)の数は同じ、最下点に注目
N = ir()
S = [[1 if x == '(' else -1 for x in list(sr())] for _ in range(N)]
pos = []
neg = []
for s in S:
    temp = 0
    mi = 0
    for x in s:
        temp += x
        if temp < mi:
            mi = temp
    if temp >= 0:
        pos.append((mi, temp))
    else:
        neg.append((mi-temp, -temp))

pos.sort(reverse=True)
neg.sort(reverse=True)
cur_p = 0; cur_n = 0
bl = True
for m, p in pos:
    if cur_p + m < 0:
        bl = False
    cur_p += p

for m, n in neg:
    if cur_n + m < 0:
        bl = False
    cur_n += n

if cur_p != cur_n:
    bl = False

print('Yes' if bl else 'No')

Submission status: Accepted

Solution code:
n = int(input())
ls, rs = [], []

def check(sl):
    h = 0
    for t in sl:
        b = h + t[0]
        if b < 0:
            return False
        h += t[1]
    return True

total = 0
for i in range(n):
    b, h = 0, 0
    S = input()
    for s in S:
        if s == '(':
            h += 1
        else:
            h -= 1
        b = min(b, h)
    if h > 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h
ls.sort(key=lambda x: x[0], reverse=True)
rs.sort(key=lambda x: x[0], reverse=True)
print('Yes' if check(ls) and check(rs) and total == 0 else 'No')

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())

S = []
for _ in range(N):
    s_i = sys.stdin.readline().strip()
    S.append(s_i)

# left bracket - right bracketを高さとした、最小の高さと最終的な高さの座標列
# ex)
# ")": (-1, -1)
# "(": (1, 1)
# "()": (1, 0)
# ")()(": (-1, 0)
# "))))(((((: (-4, 1)

plus_seqs = []
minus_seqs = []
for s_i in S:
    h = 0
    min_h = float("inf") 
    for bracket in s_i:
        if bracket == "(":
            h += 1
        else:
            h -= 1
        min_h = min(min_h, h)
            
    if h >= 0:
        plus_seqs.append((min_h, h))
    else:
        # minus_seqs.append((-1 * min_h, -1 * h))
        minus_seqs.append((min_h - h, -1 * h))

# print(plus_seqs)
# print(minus_seqs)

hight = 0
for (min_h, h) in sorted(plus_seqs, reverse=True):
    if hight + min_h < 0:
        print("No")
        sys.exit()
    hight += h

hight2 = 0
for (min_h, h) in sorted(minus_seqs, reverse=True):
    if hight2 + min_h < 0:
        print("No")
        sys.exit()
    hight2 += h

# print(hight, hight2)
if hight == hight2:
    print("Yes")
else:
    print("No")