Problem:


Score : 600 points

Problem Statement

A bracket sequence is a string that is one of the following:

An empty string;

The concatenation of (, A, and ) in this order, for some bracket sequence A ;

The concatenation of A and B in this order, for some non-empty bracket sequences A and B /

Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

1 \leq N \leq 10^6

The total length of the strings S_i is at most 10^6.

S_i is a non-empty string consisting of ( and ).

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print Yes; otherwise, print No.

Sample Input 1

2
)
(()

Sample Output 1

Yes

Concatenating (() and ) in this order forms a bracket sequence.

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

4
((()))
((((((
))))))
()()()

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
sss = [input() for _ in range(n)]

a = []
b = []
ss = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, i])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([-s, mi, ma, i])


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in heapq.heappop(heap)[-1]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in reversed(heapq.heappop(heap)[-1]):
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


ok1(a)
ok(b)
print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
bra = []
ket = []
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)
  bra.append([-mini,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)
  ket.append([-mini,now])  
check = 0
for x in bra:
  #print(x)
  check += x[1]
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
#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
#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: Time Limit Exceeded

Solution code:
n = int(input())
s = [0] * n
inc = []
zeros = []
dec = []

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((minimum, i))
    elif start < end:
        inc.append((minimum, i))
    else:
        minimum = minimum - end
        dec.append((minimum, i))

inc.sort(reverse=True)
dec.sort()


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

for (m, i) in dec:
    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: Time Limit Exceeded

Solution code:
n = int(input())
s = [0] * n
inc = []
zeros = []
dec = []

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((minimum, i))
    elif start < end:
        inc.append((minimum, i))
    else:
        minimum = minimum - end
        dec.append((minimum, i))

inc.sort(reverse=True)
dec.sort()

ans = ""
for (m, i) in inc:
    ans += s[i]

for (m, i) in zeros:
    ans += s[i]

for (m, i) in dec:
    ans += s[i]

now = 0

for c in ans:
    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
input = sys.stdin.readline

N = int(input())
array1 = []
array2 = []
for i in range(N):
    s = input()
    x1 = 0
    x2 = 0
    x3 = 0
    flag = True
    for j in range(len(s)):
        if s[j] == "(":
            if flag:
                x3 = 1
            else:
                x3 += 1
            flag = False
            x1 += 1
        elif s[j] == ")":
            x1 -= 1
            if flag:
                x2 += 1
            else:
                x3 -= 1
    if x3 < 0:
        x2 = x2 - x3
    if x1 >= 0:
        array1.append((-x2,x1))
    else:
        array2.append((x2+x1,-x2,x1))
array1.sort(reverse = True)
array2.sort(reverse = True)
sum = 0
ans = True
for i in range(len(array1)):
    if sum + array1[i][0] >= 0:
        sum += array1[i][1]
    else:
        ans = False
        break
for i in range(len(array2)):
    if sum + array2[i][1] >= 0:
        sum += array2[i][2]
    else:
        ans = False
        break
if sum != 0:
    ans = False
if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
N = int(input())
array1 = []
array2 = []
for i in range(N):
    s = input()
    x1 = 0
    x2 = 0
    x3 = 0
    flag = True
    for j in range(len(s)):
        if s[j] == "(":
            if flag:
                x3 = 1
            else:
                x3 += 1
            flag = False
            x1 += 1
        elif s[j] == ")":
            x1 -= 1
            if flag:
                x2 += 1
            else:
                x3 -= 1
    if x3 < 0:
        x2 = x2 - x3
    if x1 >= 0:
        array1.append((-x2,x1))
    else:
        array2.append((x2+x1,-x2,x1))
array1.sort(reverse = True)
array2.sort(reverse = True)
sum = 0
ans = True
for i in range(len(array1)):
    if sum + array1[i][0] >= 0:
        sum += array1[i][1]
    else:
        ans = False
        break
for i in range(len(array2)):
    if sum + array2[i][1] >= 0:
        sum += array2[i][2]
    else:
        ans = False
        break
if sum != 0:
    ans = False
if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
D, E = [], []
t,l = 0, 0
res = 0
for _ in range(N):
    S = input().rstrip()
    x,y = 0,0
    for s in S:
        if s=="(": x+=1
        else: x=max(x-1,0)
    for s in reversed(S):
        if s==")": y+=1
        else: y=max(y-1,0)
    D.append((x,y))
D.sort(key=lambda x:x[1])
t = 0
for x,y in D:
    if x-y>=0:
        if t>=y: t+=x-y
        else: print("No"); exit()
D.sort(key=lambda x:x[0])
s = 0
for x,y in D:
    if y-x>=0:
        if s>=x: s+=y-x
        else: print("No"); exit()
if t!=s: print("No")
else: print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
D, E = [], []
t,l = 0, 0
res = 0
for _ in range(N):
    S = input().rstrip()
    x,y = 0,0
    for s in S:
        if s=="(": x+=1
        else: x=max(x-1,0)
    for s in reversed(S):
        if s==")": y+=1
        else: y=max(y-1,0)
    D.append((x,y))
D.sort(key=lambda x:x[1])
t = 0
for x,y in D:
    if x-y>=0:
        if t>=y: t+=x-y
        else: print("No"); exit()
D.sort(key=lambda x:x[0])
s = 0
for x,y in D:
    if y-x>=0:
        if s>=x: s+=y-x
        else: print("No"); exit()
if t!=s: print("No")
else: print("Yes")

Submission status: Accepted

Solution code:
n = int(input())
S = [input() for _ in range(n)]
U = []
L = []
for s in S:
  l, r = 0, 0
  for t in s:
    if t == "(":
      r += 1
    else:
      if r > 0:
        r -= 1
      else:
        l += 1
  if l <= r:
    U.append((l, r-l))
  else:
    L.append((r, l-r))
U.sort()
L.sort()
s, t = 0, 0
for a, c in U:
  if s < a:
    print("No")
    exit()
  s += c
for a, c in L:
  if t < a:
    print("No")
    exit()
  t += c
if s != t:
  print("No")
  exit()
print("Yes")

Submission status: Accepted

Solution code:
n = int(input())

x = []
y = []
# left >= rightの場合、
# keft < right う

for _ in range(n):
    s = input()
    b = c = 0

    # sの中でペアにならない括弧を計算
    for t in s:
        if t == '(':
            b += 1
        else:
            if b == 0:
                c += 1
            else:
                b -= 1
    if b >= c:
        x.append((c, b))
    else:
        y.append((-b, c))
x.sort()
y.sort()
now = 0
for a, b in x:
    now -= a
    if now < 0:
        print('No')
        exit()
    now += b
for a, b in y:
    now -= b
    if now < 0:
        print('No')
        exit()
    now -= a

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N = int(readline())

    first = []
    second = []

    for _ in range(N):
        s = input()
        l, r = 0, 0
        cnt = 0
        for char in s:
            if char == "(":
                cnt += 1
            else:
                if cnt > 0:
                    cnt -= 1
                else:
                    l += 1
        r = cnt
        if r >= l:
            first.append((l, r))
        elif l > r:
            second.append((l, r))

    from operator import itemgetter

    first.sort(key=itemgetter(0))
    second.sort(key=itemgetter(1), reverse=True)

    r_cur = 0

    for x, y in first:
        r_cur -= x
        if r_cur < 0:
            return print("No")
        r_cur += y

    for x, y in second:
        r_cur -= x
        if r_cur < 0:
            return print("No")
        r_cur += y

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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 = set()
for i in range(N):
	if rremain[i] == 0:
		head += lremain[i]
		removei.add(i)
	if lremain[i] == 0:
		tail += rremain[i]
		removei.add(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")

Submission status: Accepted

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, 0, s))
            continue
            
        left = 0
        right = 0
        leftmax = 0
        for c in reversed(s):
            if c == "(":
                left += 1
            else:
                right += 1
            leftmax = max(leftmax, left - right)
        M.append((leftdiff, 0, leftmax, s))

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

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


main()

Submission status: Accepted

Solution code:
N=int(input())
S=[input() for i in range(N)]
a,b=0,0
X=[]
Y=[]
for i in range(N):
  a,b=0,0
  for j in range(len(S[i])):
    if S[i][j]=='(':
      a+=1
    else:
      a-=1
    b=min(b,a)
  b=-b
  a=a+b
  if a>b:
    X.append((b,a))
  else:
    Y.append((b,a))
P=0
Q=0
X.sort()
for i in range(len(X)):
  P=max(P,Q+X[i][0])
  Q=Q+X[i][0]-X[i][1]
Y.sort(key=lambda x:-x[1])
for i in range(len(Y)):
  P=max(P,Q+Y[i][0])
  Q=Q+Y[i][0]-Y[i][1]
if P or Q:
  print('No')
else:
  print('Yes')

Submission status: Accepted

Solution code:
# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())
L = [input() for _ in range(N)]

up = []
do = []
for li in L:
    l = li.count("(")
    r = li.count(")")
    ext_neg = 0
    ext_pos = 0
    tl, tr = 0, 0
    if 0 <= l - r:
        for op in li:
            if op == "(":
                tl += 1
            elif op == ")":
                tr += 1
            ext_neg = min(ext_neg, tl - tr)
            ext_pos = max(ext_pos, tl - tr)
        up.append((l - r, ext_neg, ext_pos))
    else:
        for op in li[::-1]:
            if op == ")":
                tl += 1
            elif op == "(":
                tr += 1
            ext_neg = min(ext_neg, tl - tr)
            ext_pos = max(ext_pos, tl - r)
        do.append((r - l, ext_neg, ext_pos))
up.sort(key=lambda tup: (-tup[1], -tup[0]))
do.sort(key=lambda tup: (-tup[1], -tup[0]))
# print(up)
# print(do)

curl = 0
for upi in up:
    dif, ext_neg, ext_pos = upi
    if curl + ext_neg < 0:
        print("No")
        exit()
    curl += dif
curr = 0
for doi in do:
    dif, ext_neg, ext_pos = doi
    if curr + ext_neg < 0:
        print("No")
        exit()
    curr += dif
if curl == curr:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
s=[input() for _ in range(n)]
d0={}
d1={}
ma=0
mab=0
for si in s:
    a,b=0,0
    for x in si:
        if x=='(':
            b+=1
        else:
            b-=1
        a=min(b,a)
    a=-a
    if b>=0:
        if a in d0:
            d0[a].append([a,b])
        else:
            d0[a]=[[a,b]]
        ma=max(ma,a)
    else:
        if a+b in d1:
            d1[a+b].append([a,b])
        else:
            d1[a+b]=[[a,b]]
        mab=max(mab,a+b)
now=0
for i in range(ma+1):
    if i not in d0:continue
    if now>=i:
        for a,b in d0[i]:
            now+=b
    else:
        print('No')
        exit()
for i in range(mab,-1,-1):
    if i not in d1:continue
    for a,b in d1[i]:
        if now>=a:
            now+=b
        else:
            print('No')
            exit()
if now==0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
N = int(input())
S = sys.stdin.read().split()
HT_high = []
HT_low = []
for s in S:
    t = 0
    h = 0
    for c in s:
        if c == "(":
            h += 1
        else:
            h -= 1
            if h < t:
                t = h
    if h >= 0:
        HT_high.append((h, t))
    else:
        HT_low.append((h, t))
HT_high.sort(key=itemgetter(1), reverse=True)
HT_low.sort(key=lambda x: x[0]-x[1], reverse=True)
h0 = 0
for h, t in HT_high + HT_low:
    if h0 + t < 0:
        print("No")
        exit()
    h0 += h
if h0 != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

n = int(input())
ls, rs = [], []
total = 0
for i in range(n):
    s = input()
    h, b = 0, 0
    for c in s:
        if c=='(':  h += 1
        else:       h -= 1
        b = min(b, h)
    if h > 0:   ls.append((b, h))       # 増減+ はb:最下点, h:増減を取る
    else:       rs.append((b-h, -h))    # 増減- は、上下左右逆さに考え、b:右から見た最下点、h:増減のマイナスを取る
    total += h
ls.sort(reverse=True)
rs.sort(reverse=True)   # 増減-は右から見るので、大きい順にsort

def chk(s):
    h = 0
    for sb, sh in s:
        b = h + sb
        if b < 0: return False
        h += sh
    return True

if (chk(ls) and chk(rs) and total==0):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import chain


N = int(input())
L = []
R = []
for i in range(N):
    S = input()
    low = 0
    var = 0

    for s in S:
        if s == '(':
            var += 1
        else:
            var -= 1
        low = min(low, var)
    
    if var >= 0:
        L.append((low, var))
    else:
        R.append((low, var))

L.sort(key=itemgetter(0), reverse=True)
R.sort(key=lambda x: x[0] - x[1])
pos = 0
for i, (low, var) in enumerate(chain(L, R)):
    if pos + low < 0:
        ans = 'No'
        break
    pos += var
else:
    ans = 'Yes' if pos == 0 else 'No'
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import chain


N = int(input())
inc = []
dec = []
for i in range(N):
    S = input()
    low = 0
    pos = 0

    for s in S:
        if s == '(':
            pos += 1
        else:
            pos -= 1
        low = min(low, pos)
    
    if pos >= 0:
        inc.append((low, pos))
    else:
        dec.append((low, pos))

inc.sort(key=itemgetter(0), reverse=True)
dec.sort(key=lambda x: x[0] - x[1])
height = 0
for i, (low, pos) in enumerate(chain(inc, dec)):
    if height + low < 0:
        ans = 'No'
        break
    height += pos
else:
    ans = 'Yes' if height == 0 else 'No'
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

def count(s):
    a = 0
    aa = 0
    b = 0
    bb = 0
    for i in range(len(s)):
        if s[i] == ")":
            if aa == 0:
                a = a + 1
            else:
                aa = aa - 1
        if s[i] == "(":
            aa = aa + 1
        if s[len(s)-1-i] == "(":
            if bb == 0:
                b = b + 1
            else:
                bb = bb - 1
        if s[len(s)-1-i] == ")":
            bb = bb + 1
    return [a, b]

N = int(input())

c = []
d = []
for i in range(N):
    s = input()
    e = count(s)
    if e[1] - e[0] >= 0: c.append(e)
    if e[0] - e[1] > 0: d.append(e)

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

c = c + d
# print(c)

f = 0
for cc in c:
    f = f - cc[0]
    if f < 0:
        print("No")
        sys.exit()
    f = f + cc[1]

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

Submission status: Accepted

Solution code:

N = int(input())
X = [input() for _ in range(N)]

ctr = [[], []]
for s in X:
    t = [0] * (len(s) + 1)
    for j in range(len(s)):
        t[j + 1] = t[j] + int(s[j] == "(") - int(s[j] == ")")

    if t[-1] > 0:
        ctr[0].append((min(t), t[-1]))
    else:
        ctr[1].append((min(t) - t[-1], -t[-1]))

flag = True
tmp = 0
for i in range(2):
    cur = 0
    for m, c in sorted(ctr[i], reverse=True):
        flag &= cur + m >= 0
        cur += c

    if i == 0:
        tmp = cur
    else:
        flag &= tmp == cur

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

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
ls = []
rs = []
z = 0
for i in range(n):
    ss = ins()
    l = r = 0
    for c in ss:
        if c=='(':
             l += 1
        else:
            if l>0:
                l -= 1
            else:
                r += 1
    rr = r
    l = r = 0
    for j in range(len(ss)-1,-1,-1):
        c = ss[j]
        if c==')':
             r += 1
        else:
            if r>0:
                r -= 1
            else:
                l += 1
    r = rr
    if l>r:
        ls.append((r,l-r))
    elif l<r:
        rs.append((l,r-l))
    else:
        z = max(z,r)
ls.sort()
rs.sort()
#ddprint(ls)
#ddprint(rs)
#ddprint(z)
l = r = 0
for rr,ll in ls:
    if l<rr:
        print('No')
        exit()
    l = l+ll
for ll,rr in rs:
    if r<ll:
        print('No')
        exit()
    r = r+rr
print('Yes' if l==r>=z else 'No')

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(S):
    N = len(S)
    L = np.empty(N, np.int64)
    R = np.empty(N, np.int64)

    x = y = 0
    n = 0
    for s in S:
        if s == 0:
            y += 1
        elif s == 1:
            if y:
                y -= 1
            else:
                x += 1
        else:
            L[n], R[n] = x, y
            n += 1
            x = y = 0

    L, R = L[:n], R[:n]
    L1, R1 = L[L > R], R[L > R]
    L2, R2 = L[L <= R], R[L <= R]

    ind = R1.argsort()
    L1, R1 = L1[ind], R1[ind]

    ind = L2.argsort()[::-1]
    L2, R2 = L2[ind], R2[ind]

    L = np.concatenate((L1, L2))
    R = np.concatenate((R1, R2))

    n = 0
    for i in range(len(L)):
        if n < R[i]:
            return False
        n += L[i] - R[i]
    return n == 0

N = int(readline())
S = np.array(list(read()), np.int64) - ord('(')

print('Yes' if main(S) else 'No')

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    lx = []
    rx = []
    for i in range(n):
        a = 0
        cnt = 0
        for j in input():
            if j == '(':
                cnt += 1
            else:
                cnt -= 1
            a = min(a, cnt)
        
        if cnt >= 0:
            lx.append((a, cnt))
        else:
            rx.append((a, cnt))
    lx.sort(key= lambda x: -x[0]) # -aの昇順
    rx.sort(key= lambda x: x[0]-x[1]) # -bの昇順(bの降順)
    total = 0
    check = True
    for x,cnt in (lx+rx):
        if total + x < 0:
            check = False
            break
        total += cnt
    if total == 0 and check:
        print('Yes')
    else:
        print("No")
    




if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = []
B = []

for i in range(N):
    a = 0  # (の個数
    b = 0  # )の個数
    c = 0  # 始点に対する最下点の高さ（(を+1,)を-1とみなす）
    for j in range(len(S[i])):
        if S[i][j] == '(':
            a += 1
        else:
            b += 1
            c = min(a-b,c)
    if a-b >= 0:
        A.append((a-b,c))  # (何個高くなるか,最下点の相対的高さ)
    else:
        B.append((a-b,c))  # (何個高くなるか,最下点の相対的高さ)

a,b = len(A),len(B)

from operator import itemgetter

A = sorted(A,key=itemgetter(1),reverse=True)

c = 0  # Aの元を全て繋げた時,何個高くなるか

for i in range(a):
    if c + A[i][1] < 0:
        print('No')
        exit()
    else:
        c += A[i][0]

for i in range(b):
    B[i] = (-B[i][0],B[i][1]-B[i][0])

B = sorted(B,key=itemgetter(1),reverse=True)

d = 0  # Bの元を全て繋げた時,何個高くなるか

for i in range(b):
    if d + B[i][1] < 0:
        print('No')
        exit()
    else:
        d += B[i][0]

if c == d:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

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

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


tmp_cnt_plus  = []
tmp_cnt_minus = []

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


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


sum_bracket = 0
flag = True

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


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

Submission status: Accepted

Solution code:
def check():
    N = int(input())
    plus,minus = [],[]
    for i in range(N):
        S = input()
        now = 0
        mini = 0
        for s in S:
            if s=='(':
                now += 1
            else:
                now -= 1
                mini = min(mini,now)
        if now>=0:
            plus.append([mini,now])
        else:
            minus.append([now-mini,now])
    plus.sort(reverse=True)
    minus.sort(reverse=True)
    now = 0
    for a,b in plus:
        if now + a <0:
            return 'No'
        now += b
    for a,b in minus:
        if now + b-a <0:
            return 'No'
        now += b
    if now > 0:
        return 'No' 
    return 'Yes'
print(check())

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    up = []
    down = []
    for _ in range(n):
        height = 0
        m = 0
        for si in input():
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if height >= 0:
            up.append([m, height])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([i for _, i in up]) - sum([i for _, i in down]) != 0:
        print("No")
        return
    h = 0
    for mi, hi in up:
        if h+mi < 0:
            print("No")
            return
        h += hi
    h = 0
    for mi, hi in down:
        if h+mi < 0:
            print("No")
            return
        h += hi
    print("Yes")
    return
            

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    s = S()
    ret = 0
    ret2 = 0
    for i in s:
        if ret and i == ')':
            ret -= 1
        elif i == '(':
            ret += 1
        else:
            ret2 += 1
    if ret2 > ret:
        plus += [(ret, ret2)]
    else:
        minus += [(ret, ret2)]


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

now = 0
for x, y in L:
    now -= x
    if now < 0:
        print("No")
        exit()
    now += y

if now:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    s = S()
    ret = 0
    ret2 = 0
    for i in s:
        if ret and i == ')':
            ret -= 1
        elif i == '(':
            ret += 1
        else:
            ret2 += 1
    if ret2 > ret:
        plus += [(ret, ret2)]
    else:
        minus += [(ret, ret2)]


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

now = 0
for x, y in L:
    if x > now:
        print("No")
        exit()
    now = now - x + y

if now:
    print("No")
else:
    print("Yes")