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:
n = int(input())
bra = []
ket = []
c = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    bra.append([-mini,now])
  c.append(now)
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    ket.append([-mini,now])  
check = 0
for x in c:
  #print(x)
  check += x
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
n = len(bra)
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)

ket.sort()
now = 0
here = -1
n = len(ket)
#print(bra)
pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)
print('Yes')

Submission status: Accepted

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

def solve() :
  T = []
  for s in S :
    open = 0
    close = 0
    for c in s :
      if c == ')' :
        if open > 0 :
          open -= 1
        else :
          close += 1
      else :
        open += 1
    T.append((open, close))
  
  if sum(op - cl for op, cl in T) != 0 :
    return 'No'
  
  inc = []
  dec = []
  for op, cl in T :
    if op >= cl :
      inc.append((cl, op))
    else :
      dec.append((op, cl))
      
  inc.sort()
  open = 0
  for cl, op in inc :
    if open >= cl :
      open += op - cl
    else :
      return 'No'
  
  close = 0
  dec.sort()
  for op, cl in dec :
    if close >= op :
      close += cl - op
    else :
      return 'No'
      
  return 'Yes'
      
print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    l_p_only = []
    r_p_only = []
    r_p_l_p = []
    for _ in range(n):
        s = input()
        left_cnt = 0
        right_cnt = 0
        for char in s:
            if char == ')':
                if left_cnt > 0:
                    left_cnt -= 1
                else:
                    right_cnt += 1
            else:
                left_cnt += 1
        if left_cnt == 0 and right_cnt == 0:
            pass
        elif right_cnt == 0:
            l_p_only.append(left_cnt)
        elif left_cnt == 0:
            r_p_only.append(- right_cnt)
        else:
            r_p_l_p.append([- right_cnt, left_cnt])
    # print(l_p_only)
    # print(r_p_l_p)
    # print(r_p_only)

    current_left = sum(l_p_only)
    pos = []
    neg = []
    for elm in r_p_l_p:
        if elm[0] + elm[1] >= 0:
            pos.append(elm)
        else:
            neg.append(elm)
    pos.sort(key=lambda x: x[0], reverse=True)    # 負の値が大きい順、0 に近い順
    for elm in pos:
        current_left += elm[0] 
        if current_left >= 0:
            current_left += elm[1]
        else:
            print('No')
            exit()
    neg.sort(key=lambda x: x[0])    # 負の値が小さい順、- に大きい順に最初のうちにやっておく
    for elm in neg:
        current_left += elm[0]
        if current_left >= 0:
            current_left += elm[1]
        else:
            print('No')
            exit()
    if current_left >= 0 and current_left == - sum(r_p_only):
        print('Yes')
    else:
        print('No')



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

n = int(input())
s = read().split()

dp = []
dn = []
for i in s:
    a = 0
    d = 0
    for j in i:
        if j == "(": d+= 1
        else: d -= 1
        if d < a: a = d
    
    #print(a,d,i)    
    if d >= 0:    
        dp.append((a,d))
    else:
        dn.append((a-d,-d))
    
dp.sort()
dn.sort()

def check(dp):
    D = 0
    while dp:
        a,d = dp.pop()
        if D+a < 0: return False
        D += d
    return [D]

#print(dp)
#print(dn)
a = check(dp)
b = check(dn)
#print(a,b)

if a==False or b==False:
    print("No")
else:
    if a[0] != b[0]:
        print("No")
    else:
        print("Yes")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = [list(input()) for _ in range(n)]
    L_cnt = []
    R_cnt = []
    LR_cnt = []
    min_l,min_r = 10**6,10**6
    for i in range(n):
        t = s[i]
        flag = 0
        l = 0
        r = 0
        for j in range(len(t)):
            if not flag and t[j] == ')':
                r += 1
            elif t[j] == '(':
                flag = 1
                l += 1
            else:
                l -= 1
                if l == 0:
                    flag = 0
        if r == 0 and l == 0:
            continue
        if r == 0:
            L_cnt.append(l)
        elif l == 0:
            R_cnt.append(r)
        else:
            LR_cnt.append([l,r])
            min_l = min(min_l,l)
            min_r = min(min_r,r)
    L,R = sum(L_cnt),sum(R_cnt)
    if not LR_cnt:
        if L == R:
            print('Yes')
            return
        else:
            print('No')
            return
    if not (L_cnt and R_cnt):
        print('No')
        return
    box1 = []
    box2 = []
    for i in range(len(LR_cnt)):
        if L >= LR_cnt[i][1] and LR_cnt[i][1] <= LR_cnt[i][0]:
            L += LR_cnt[i][0] - LR_cnt[i][1]
        elif LR_cnt[i][1] <= LR_cnt[i][0]:
            box1.append(LR_cnt[i])
        else:
            box2.append(LR_cnt[i])
    for i in range(len(box1)):
        L -= box1[i][1]
        if L < 0:
            print('No')
            return
        L += box1[i][0]
    for i in range(len(box2)):
        L -= box2[i][1]
        if L < 0:
            print('No')
            return
        L += box2[i][0]
    if L == R:
        print('Yes')
    else:
        print('No')
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for lp in range(N):

    S = input()

    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            dep += 1
        else:
            dep -= 1

        mindep = min(dep,mindep)

    if dep >= 0:
        pl_d.append([mindep,dep])
    else:
        mi_d.append([mindep-dep,-1 * dep])

pl_d.sort()
mi_d.sort()
pl_d.reverse()
mi_d.reverse()

#print (pl_d,mi_d)

nowp = 0

import sys
for i in range(len(pl_d)):

    nd,np = pl_d[i]

    if nowp + nd < 0:
        print ("No")
        sys.exit()

    nowp += np

nowm = 0

import sys
for i in range(len(mi_d)):

    nd,np = mi_d[i]

    if nowm + nd < 0:
        print ("No")
        sys.exit()

    nowm += np


if nowp != nowm:
    print ("No")
else:
    print ("Yes")

Submission status: Accepted

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

n = int(input())
S = [input() for i in range(n)]

A = [[], [], []]

u = 0

for i in range(n):
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            a += 1
        else:
            a -= 1
            b = min(b, a)
    u += a
    if a > 0:
        A[0].append([b, a])
    elif a == 0:
        A[1].append([b, a])
    else:
        A[2].append([a-b, a])



if u != 0:
    print("No")
    sys.exit()

# print(A)

A[0].sort(reverse=True)
A[2].sort()

# print(A)


ng = 0
a = 0
for i in range(len(A[0])):
    a += A[0][i][0]
    if a < 0:
        ng = 1
        break
    a += A[0][i][1]-A[0][i][0]
    if a < 0:
        ng = 1
        break

if ng == 0:
    for i in range(len(A[1])):
        a += A[1][i][0]
        if a < 0:
            ng = 1
            break
        a -= A[1][i][0]

if ng == 0:
    a = 0
    for i in range(len(A[2])):
        aa = A[2][i][1]
        bb = aa-A[2][i][0]
        a -= A[2][i][0]
        if a < 0:
            ng = 1
            break
        a += -bb
        if a < 0:
            ng = 1
            break

# print(a)

if ng == 1:
    print("No")
else:
    print("Yes")

Submission status: Accepted

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

n = int(input())
ss = read().split()

cnt_p = []
cnt_m = []
for i in range(n):
    left = 0
    right = 0
    for s in ss[i]:
        if(s == '('):
            left += 1
        elif(s == ')'):
            if(left > 0):
                left -= 1
            else:
                right += 1
    if(left-right > 0):
        cnt_p.append((right,left))
    else:
        cnt_m.append((right,left))


cnt_p = sorted(cnt_p, key=lambda x: (x[0]))
cnt_m = sorted(cnt_m, key=lambda x: (x[1]*-1))
cnt = cnt_p + cnt_m
num = 0
for right,left in cnt:
    num -= right
    if(num < 0):
        print('No')
        exit()
    num += left

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

Submission status: Accepted

Solution code:
n = int(input())
s = [0] * n
inc = [[] for _ in range(1100000)]
zeros = []
dec = [[] for _ in range(1100000)]

for i in range(n):
    s[i] = input()
    start = 0
    minimum = 0
    now = 0
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        minimum = min(minimum, now)
    end = now
    
    if end == 0:
        zeros.append(i)
    elif start < end:
        inc[minimum].append(i)
    else:
        minimum = minimum - end
        dec[minimum].append(i)

now = 0
for m in range(0, -1000000, -1):
    for i in inc[m]:
        for c in s[i]:
            if c == '(':now += 1
            else: now -= 1
            if now < 0:
                print("No")
                exit()
        
for i in zeros:
    for c in s[i]:
        if c == '(':now += 1
        else: now -= 1
        if now < 0:
            print("No")
            exit()
            
for m in range(-1000000, 1):
    for  i in dec[m]:
        for c in s[i]:
            if c == '(':now += 1
            else: now -= 1
            if now < 0:
                print("No")
                exit()
                
if now != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
import heapq as hq

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n = ni()
l = [ns() for _ in range(n)]
gu = list()
gd = list()
c = 0
lm = None
for i in range(n):
    s = l[i]
    t = 0
    m = 0
    for x in s:
        if x == '(':
            t += 1
        else:
            t -= 1
            if m > t:
                m = t
    c += t
    if t > 0:
        gu.append((m, t))
    else:
      if t == m and (lm is None or m < lm):
        t = lm
        m, lm = lm, m
      if m is not None:
        gd.append((m, -t))
if c != 0 or lm is None:
    print('No')
    exit(0)
gu.sort(reverse=True)
gd.sort()
cur = 0
q = list()
for m, t in gu:
    if cur + m < 0:
        print('No')
        exit(0)
    cur += t
for m, t in gd:
    if cur + m < 0:
        print('No')
        exit(0)
    cur -= t

print('Yes')

Submission status: Accepted

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

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

D = []
L, R = [], []
for s in S:
    l, r = 0, 0
    for c in s:
        if c == ')':
            if l > 0:
                l -= 1
            else:
                r += 1
        else:
            l += 1
    if l == 0 and r == 0:
        pass
    elif l == 0:
        R.append(r)
    elif r == 0:
        L.append(l)
    else:
        D.append((l, r))

L = sum(L)
R = sum(R)

inc = []
dec = []
for l, r in D:
    if l > r:
        inc.append((l, r))
    else:
        dec.append((l, r))

inc.sort(key=lambda x:x[1])
dec.sort(key=lambda x:-x[1])

D = inc + dec

for i, (l,r) in enumerate(D):
    L -= r
    if L < 0:
        print('No')
        exit(0)
    L += l

if L == R:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

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

PLUS=[]
MINUS=[]
ZERO=[0]
for br in S:
    NOW=0
    MIN=0
    for b in br:
        if b=="(":
            NOW+=1
        else:
            NOW-=1
            MIN=min(MIN,NOW)

    if NOW>0:
        PLUS.append((NOW,MIN))
    elif NOW<0:
        br2=br[::-1]

        NOW=0
        MIN=0
        for b in br2:
            if b==")":
                NOW+=1
            else:
                NOW-=1
                MIN=min(MIN,NOW)
        MINUS.append((NOW,MIN))
        
    else:
        ZERO.append(MIN)


from operator import itemgetter
PLUS.sort(key=itemgetter(1),reverse=True)

NOW0=0
for p,m in PLUS:
    if NOW0>=-m:
        NOW0+=p
    else:
        print("No")
        sys.exit()

MINUS.sort(key=itemgetter(1),reverse=True)

NOW1=0
for p,m in MINUS:
    if NOW1>=-m:
        NOW1+=p
    else:
        print("No")
        sys.exit()

if NOW0==NOW1 and NOW0>=-min(ZERO):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def f(S):
    worst = 0
    res = 0
    for s in S:
        if(s=='('):
            res += 1
        else:
            res -= 1
        worst = min(worst, res)
    return worst, res
def main():
    N=I()
    S=[ST() for _ in range(N)]
    
    AB_nega=[]
    AB_nonnega=[]
    for i in range(N):
        a,b = f(S[i])
        if b<0:
            AB_nega.append((a,b))
        else:
            AB_nonnega.append((a,b))
    
    AB_nega.sort(key=lambda x:-x[0]+x[1], reverse =True)
    AB_nonnega.sort(reverse = True)

    # print(AB_nega)
    # print(AB_nonnega)

    now = 0
    for a,b in AB_nonnega:
        if(now+a < 0):
            print("No")
            return
        now += b
        # print(now,"#######")
    
    
    for a,b in AB_nega:
        if(now+a<0):
            print("No")
            return
        now += b
        # print(now,"#########")
    if now == 0:
        print('Yes')
    else:
        print("No")


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
dec_special = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    elif minima < fin:
        dec_special.append((minima, fin))
    else:
        decreasing.append((minima, fin))

increasing.sort(reverse=True)
decreasing.sort()
dec_special.sort()

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in dec_special:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
def I():
    s = input()
    mi = 0
    su = 0
    t = 0
    for a in s:
        if a == "(":
            t += 1
        else:
            t -= 1
            mi = min(mi, t)
    return (mi, t)

X = [I() for _ in range(N)]
if sum([x[1] for x in X]):
    print("No")
    exit()

X = sorted(X, key = lambda x: -10**10 if x[0] == 0 else -10**9 - x[0] if x[1] > 0 else x[0] - x[1])
T = 0
for mi, t in X:
    if T + mi < 0:
        print("No")
        exit()
    T += t
print("Yes")

Submission status: Accepted

Solution code:
n=int(input())
sl=0
sr=0
sz=0
lr=[]
rl=[]
for i in range(n):
    s=input()
    l=0
    r=0
    z=0
    for j in s:
        if j=="(":
            l+=1
        else:
            r+=1
        z=max(z,r-l)
    sl+=l
    sr+=r
    if z==0 and l>=r:
        sz+=l-r
    elif l>=r:
        lr.append((z,l-r))
    else:
        rl.append((z,l-r))
if sl!=sr:
    print("No")
    quit()
lr.sort()
for z,i in lr:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
rl.sort(key=lambda x:x[0]+x[1] ,reverse=True)
for z,i in rl:
    if sz<z:
        print("No")
        quit()
    else:
        sz+=i
print("Yes")

Submission status: Accepted

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

MAX = 10**6
N = int(input())
Ss = [input().rstrip() for _ in range(N)]

def calc(S):
    stack = []
    for s in S:
        if s == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            stack.append(s)
    le = 0
    ri = 0
    for s in stack:
        if s == ")":
            le += 1
        else:
            ri += 1
    return le, ri

Ps = [[] for _ in range(MAX+1)]
Qs = [[] for _ in range(MAX+1)]
for S in Ss:
    le, ri = calc(S)
    if ri >= le:
        Ps[le].append(ri-le)
    else:
        Qs[ri].append(le-ri)

T = 0
ok = True
for le, P in enumerate(Ps):
    if P and T < le:
        ok = False
        break
    else:
        T += sum(P)

U = 0
for ri, Q in enumerate(Qs):
    if Q and U < ri:
        ok = False
        break
    else:
        U += sum(Q)

if T != U:
    ok = False
print("Yes" if ok else "No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
br = [input().rstrip() for i in range(n)]
ls = []
numsum = 0
charge = 0
for i in range(n):
  s = br[i]
  need = 0
  num = 0
  for t in s:
    if t == "(":
      num += 1
    else:
      num -= 1
    need = max(need,-num)
  numsum += num
  if need == 0:
    charge += num
  else:
    ls.append([need,num])
if numsum != 0:
  print("No")
  exit()
ls.sort()
l = len(ls)
vis = [0]*l
for i,x in enumerate(ls):
  need,num = x
  if need <= charge and num >= 0:
    charge += num
    ls[i][0] = -1
ls.sort(key = lambda x:x[0]+x[1],reverse=True)
for i in range(l):
  need,num = ls[i]
  if need == -1:
    continue
  if need > charge:
    print("No")
    exit()
  charge += num
print("Yes")

Submission status: Accepted

Solution code:
import sys
N = int(input())
dif = [0] * N
mini = [0] * N
for _ in range(N):
    S = input()
    m = 0
    now = 0
    for i in range(len(S)):
        if S[i] == '(':
            now += 1
        else:
            now -= 1
        m = min(m, now)
    dif[_] = now
    mini[_] = m

sum = 0
for i in range(N):
    sum += dif[i]
if sum != 0:
    print('No')
    sys.exit()

plus = []
minus = []
for i in range(N):
    if dif[i] >= 0:
        plus.append((mini[i], dif[i]))
    else:
        minus.append((dif[i] - mini[i], mini[i], dif[i]))
plus.sort(reverse=True)
minus.sort(reverse=True)


now = 0
for i in range(len(plus)):
    if now + plus[i][0] < 0:
        print('No')
        sys.exit()
    now += plus[i][1]

for i in range(len(minus)):
    if now + minus[i][1] < 0:
        print('No')
        sys.exit()
    now += minus[i][2]
print('Yes')

Submission status: Accepted

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0)
n = int(input())
# S = [tuple() for _ in range(n)]
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1]
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')':
            cnt += 1
            M = max(M,cnt)
        else:
            cnt -= 1
            # m = min(m,cnt)
    cnt = 0
    for t in s[::-1]:
        if t == ')':
            cnt += 1
            # M = max(M,cnt)
        else:
            cnt -= 1
            m = min(m,cnt)
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XY_pos = []
    XY_neg = []
    balance = 0
    for _ in range(N):
        S = input().rstrip('\n')
        st = []
        for s in S:
            if s == "(":
                st.append(s)
            else:
                if st:
                    if st[-1] == "(":
                        st.pop()
                    else:
                        st.append(s)
                else:
                    st.append(s)
        x = y = 0
        for s in st:
            if s == "(":
                y += 1
            else:
                x += 1
        balance += x - y
        if x > y:
            XY_neg.append((x, y))
        else:
            XY_pos.append((x, y))
    if balance:
        print("No")
        exit()

    XY_pos.sort(key=lambda p: p[0])
    val = 0
    for x, y in XY_pos:
        if x > val:
            print("No")
            #print(x, y, val)
            exit()
        val += y - x
    XY_neg.sort(key=lambda p: p[1], reverse=True)
    for x, y in XY_neg:
        if x > val:
            print("No")
            #print(x, y, val)
            exit()
        val += y - x
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
flag = 0
for i in range(N):
    s = input().strip()
    if s=="(":
        A.append(s)
    else:
        if A[-1]=="(":
            A.pop()
        else:
            flag = 1
            break
if flag==0:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
N = int(input())
lremain = []
rremain = []

for i in range(N):
	S = input()
	left = 0
	right = 0
	for c in S:
		if c == ".":
			left += 1
		else:
			if left == 0:
				right += 1
			else:
				left -= 1
	if left == 0 and right == 0:
		continue
	lremain.append(left)
	rremain.append(right)

N = len(lremain)

if sum(lremain) != sum(rremain):
	print("No")
	exit()

head = 0
tail = 0
removei = []
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.append(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.append(i)

lnr = []
for i in range(N):
	if not i in removei:
		lnr.append((lremain[i], rremain[i]))

N = len(lnr)
lnr.sort(key = lambda x: (x[1], -x[0]))

for i in range(N):
	if head < lnr[i][1]:
		print("No")
		exit()
	head -= lnr[i][1]
	head += lnr[i][0]

if head == tail:
	print("Yes")
else:
	print("No")
	
	
23, 31, 41, 43 wa
1, 2, 3, 4, tle

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right
        rightmax = rightmax
        if leftdiff >= 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    MM = list(sorted(M, key=lambda _e: _e[0], reverse=True))
    used = [False]*len(MM)
    for i in range(MM):
        for j in range(MM):
            if used[j]:
                continue
            e = MM[j]            
            if nleft - e[1] >= 0:
                used[j] = True
                nleft += e[0]
                break
        else:
            print("No")
            return

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


main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right       
        if leftdiff >= 0:
            P.append((leftdiff, rightmax, s))
        else:
            M.append((leftdiff, rightmax, s))

    R = []
    for e in sorted(P, key=lambda _e: _e[1]):
        R.push(e[2])
    for e in sorted(M, key=lambda _e: _e[1], reverse=True):
        R.push(e[2])

    left = 0    
    for c in "".join(R):
        if c == "(":
            left += 1
        else:
            left -= 1
        if left < 0:
            print("No")
            return
    if left == 0:
        print("Yes")
    else:
        print("No")


main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    P = []
    M = []
    for i in range(N):
        s = input()
        st = ST()
        left = 0
        right = 0
        rightmax = 0
        for c in s:
            if c == "(":
                left += 1
            else:
                right += 1
            rightmax = max(rightmax, right - left)
        leftdiff = left - right
        rightmax = rightmax
        if leftdiff > 0:
            P.append((leftdiff, rightmax))
        else:
            M.append((leftdiff, rightmax))

    nleft = 0
    for e in sorted(P, key=lambda _e: _e[1]):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

    for e in sorted(P, key=lambda _e: _e[1], reversed=True):
        if nleft - e[1] < 0:
            print("No")
            return
        nleft += e[0]

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


main()

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
b=[]
for i in range(n):
  s=input()
  overall=0
  minimum=0
  current=0
  for j in range(len(s)):
    if s[j]=='(':
      current+=1
    else:
      current-=1
    minimum=min(current,minimum)
  overall=current
  if overall>=0:
    a.append([overall,minimum])
  else:
    b.append([overall,minimum])
finalsum=0
a=sorted(a, key=lambda t:t[1])
a.reverse()
b=sorted(b, key=lambda t:t[1])
for i in a:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
for i in b:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
if finalsum==0:
  print('Yes')
else:
  print('No')