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:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class SegmentTree:
        def __init__(self,n,segfunc,ide_ele):
            self.segfunc=segfunc
            self.ide_ele=ide_ele
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(len(iter)):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=[input() for i in range(N)]
    P=0
    M=0
    c=0
    Seg=SegmentTree(10**6+1,lambda a,b:max(a,b),-INF)
    l_PM=defaultdict(list)
    stack=defaultdict(list)
    minus=set()
    for i,s in enumerate(S):
        p=0
        m=0
        for x in s:
            if x=='(':
                p+=1
            else:
                if p>0:
                    p-=1
                else:
                    m+=1
        if m==0 and p>0:
            P+=p
        elif p==0 and m>0:
            M+=m
        elif p>0 and m>0:
            c+=1
            minus.add(m)
            stack[m].append(p-m)
    
    minus=list(minus)
    minus.sort()
    for x in minus:
        stack[x].sort()
        if x<=P:
            while stack[x]:
                y=stack[x].pop()
                if y>=0:
                    c-=1
                    P+=y
                else:
                    Seg.update(x,y)
                    l_PM[y].append(x)
                    break
        else:
            y=stack[x].pop()
            Seg.update(x,y)
            l_PM[y].append(x)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF or P+x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        res=bisect_right(l_PM[x],P)-1
        index=l_PM[x][res]
        del l_PM[x][res]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
            l_PM[y].append(index)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
sp=[]
sn=[]
for i in range(n):
    s=input().rstrip()
    m=0
    temp=0
    for j in s:
        if j=='(':
            temp+=1
        else:
            temp-=1
        m=min(m,temp)
    m=-m
    if temp>=0:
        sp.append((m,temp))
    else:
        sn.append((m+temp,-temp))
sp.sort()
sn.sort()
vp=0
for i in sp:
    if vp-i[0]<0:
        print('No')
        sys.exit()
    else:
        vp+=i[1]
vn=0
for i in sn:
    if vn-i[0]<0:
        print('No')
        sys.exit()
    else:
        vn+=i[1]
if vp==vn:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Accepted

Solution code:
n = int(input())
lr1, lr2 = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, r = 0, 0
    tmp = 0
    for i in range(m):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        l = max(l, tmp)
    tmp = 0
    for i in range(m):
        if s[m-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        r = max(r, tmp)

    res += r - l
    if r - l >= 0:
        lr1.append((l, r))
    else:
        lr2.append((l, r))

if res != 0:
    print('No')
    exit()

lr1.sort(key=lambda x: x[0])
lr2.sort(key=lambda x: x[1])

flg1, flg2 = True, True

n1, n2 = len(lr1), len(lr2)
tmp = 0
for i in range(n1):
    l, r = lr1[i]
    tmp -= l
    if tmp < 0:
        flg1 = False
    tmp += r

tmp = 0
for i in range(n2):
    l, r = lr2[i]
    tmp -= r
    if tmp < 0:
        flg2 = False
    tmp += l

if flg1 and flg2:
    print('Yes')

else:
    print('No')

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    pos = []
    neg = []
    tot = 0
    for i in range(N):
        tmp = 0
        b = 0
        for c in sr():
            if c == '(':
                tmp += 1
            else:
                tmp -= 1
                b = min(b, tmp)
        if tmp > 0:
            pos.append([tmp, b])
        else:
            neg.append([-tmp, b-tmp])
        tot += tmp
    if tot != 0:
        print('No')
        return
    pos = sorted(pos, key=lambda x: (x[1], x[0]))[::-1]
    neg = sorted(neg, key=lambda x: (x[1], x[0]))[::-1]
    c = 0
    for p in pos:
        t, b = p
        if c+b < 0:
            print('No')
            return
        c += t
    c = 0
    for n in neg:
        t, b = n
        if c+b < 0:
            print('No')
            return
        c += t
    print('Yes')
    return
resolve()

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
plus, minus = [], []
for _ in range(n):
	s = input()
	mi, cur = 0, 0
	for i in range(len(s)):
		if s[i] == "(":
			cur += 1
		else:
			cur -= 1
		mi = min(mi, cur)
	if cur >= 0:
		plus.append((mi, cur))
	else:
		minus.append((mi, cur))

plus.sort(key=lambda x: -x[0])
minus.sort(key=lambda x: x[0] - x[1])
res = plus + minus

cur = 0
for m, t in res:
	if cur + m < 0:
		print("No")
		exit()
	cur += t

if cur != 0:
	print("No")
	exit()
print("Yes")

Submission status: Accepted

Solution code:

n = int(input())
s = [list(input()) for i in range(n)]
r = []
l = []
ans = 0
for i in s:
    now = 0
    c = 0
    for j in i:
        if j =="(":
            now += 1
        else:
            now -= 1
        c = min(c,now)
    if c == 0:
        ans += now
    elif now >= 0:
        l.append([c,now])
    else:
        r.append([c-now,now])

l.sort(reverse =True)
r.sort()
for i,j in l:
    if ans + i < 0:
        print("No")
        exit()
    else:
        ans += j

for i,j in r:
    if ans +i+j < 0:
        print("No")
        exit()
    else:
        ans += j
if ans == 0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

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

n = int(input())
increasing = []
decreasing = []
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))
    else:
        decreasing.append((minima - fin, fin))

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

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

Submission status: Accepted

Solution code:
n = int(input())
L = []
R = [] # Rは右から見た値を入れる
for _ in range(n):
  s = input()
  btm = 0
  total = 0
  for c in s:
    if c == "(":
      total += 1
    else:
      total -= 1
    btm = min(btm, total)
  if total > 0:
    L.append((btm, total))
  else:
    R.append((btm - total, - total))
    
L.sort(key=lambda x: (-x[0], -x[1]))
R.sort(key=lambda x: (-x[0], -x[1]))

Lcrr_end = 0
for b, e in L:
  if Lcrr_end + b < 0:
    print("No")
    exit()
  Lcrr_end += e

Rcrr_end = 0
for b, e in R:
  if Rcrr_end + b < 0:
    print("No")
    exit()
  Rcrr_end += e

if Lcrr_end - Rcrr_end == 0:
  print("Yes")
else:
  print("No")

Submission status: Accepted

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

n = int(input())
cnt = 0
decrement = 0
profit = []
loss = []

for _ in range(n):
    s = input().rstrip()
    min_p = 0
    end_p = 0
    point = 0
    for c in s:
        if c == '(':
            point += 1
        elif c == ')':
            point -= 1
            if point < min_p:
                min_p = point
    else:
        end_p = point
    if 0 <= min_p:
        cnt += end_p
    else:
        if min_p == end_p:
            decrement += end_p
        else:
            if 0 <= end_p:
                profit.append((min_p, end_p))
            else:
                loss.append((min_p, end_p))



profit.sort()
while profit:
    min_p, end_p = profit.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p


loss.sort(reverse=True)
while loss:
    min_p, end_p = loss.pop()
    if cnt+min_p < 0:
        print('No')
        exit()
    cnt += end_p

print('Yes' if cnt+decrement == 0 else 'No')

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    plus, minus = [], []
    readline = stdin.readline
    n = int(readline())
    for _ in range(n):
        s = readline().rstrip()
        if 2 * s.count('(') - len(s) > 0:
            plus.append(s)
        else:
            minus.append(s)
    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)

    sum = 0
    for v in ''.join(plus + minus):
        sum = sum + (1 if v == '(' else -1)
        if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    plus, minus = [], []
    readline = stdin.readline
    n = int(readline())
    for _ in range(n):
        s = readline().rstrip()
        if 2 * s.count('(') - len(s) > 0:
            plus.append(s)
        else:
            minus.append(s)
    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)

    sum = 0
    for v in ''.join(plus):
        sum = sum + (1 if v == '(' else -1)
        if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

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())
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
            # print('+cnt:{}'.format(cnt))
            M = max(M,cnt) #'('が多い場合はcnt=0,')'が多い場合はcntは'('と')'の個数の差
            # print('M:{}'.format(M))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: #後ろから探索
        if t == ')':
            cnt += 1
            # print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
            m = min(m,cnt) #')'が多い場合はcnt=0,'('が多い場合はcntは'('と')'の個数の差
            # print('m:{}'.format(m))
    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:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Submission status: Accepted

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Submission status: Accepted

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Submission status: Accepted

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if m+c<0:print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Submission status: Accepted

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if m+c<0:
        print("No");break
    m+=d
else:
    print("No" if m else "Yes")

Submission status: Accepted

Solution code:
from itertools import *
n,*s=open(0).read().split()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*s_.count("(")-len(s_)] for s_ in s]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
n,*s=open(0).read().split()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*s_.count("(")-len(s_)] for s_ in s]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c,d in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c<0:
        print("No");break
    now+=d
else:
    print("No" if now else "Yes")

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");break
    now+=c[1]
else:
    print("No" if now else "Yes")

Submission status: Accepted

Solution code:
n = int(input())
flag = 0
ML = []
MM = []
MR = []
L = 0
R = 0
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
            saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((-cur + saisho, -cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort(reverse=True)
leftnow = 0
for saisho, delta in ML:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
for saisho, delta in MM:
    if leftnow + saisho < 0:
        flag = 1
    leftnow += delta
rightnow = 0
for saisho, delta in MR:
    if rightnow + saisho < 0:
        flag = 1
    rightnow += delta

if rightnow != leftnow:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Submission status: Accepted

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
#pypyではinitialだめ
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]

now=0
v=list(filter(lambda x:x[1]>=0,st))
w=list(filter(lambda x:x[1]<0,st))
v.sort()
w.sort(key=lambda z:z[1]-z[0])

for c in chain(v[::-1],w[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Submission status: Accepted

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=0
v=list(filter(lambda x:x[0]>=0,st))
w=list(filter(lambda x:x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Accepted

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

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=list(map(lambda x:2*x.count("(")-len(x),s))
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Accepted

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Accepted

Solution code:
n = int(input())
L, R = [], []
for i in range(n):
    a, b = 0, 0
    for c in input():
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    if -a + b > 0:
        L.append((a, b))
    else:
        R.append((a, b))
L.sort(key=lambda x: x[0])
R.sort(key=lambda x: x[1], reverse=True)
x = 0
for a, b in L + R:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
# "()"となっている部分は全て削除できる
# "("だけで構成されているものは、ポイントuP
# ")"だけで構成されているものは、ポイントDOWN(最後に使う)
# ")("で構成されているものは、")"より"("の方が多いものと少ないものと同じものに分ける
# ・")"より"("のほうが多いものを、")"の数が少ない順に使っていく
# ・")"と"("の数が同じものを使う
# ・")"より"("のほうが少ないものを、")"の数が多い順に使っていく

import sys
readline = sys.stdin.readline

N = int(readline())
opencnt = 0
closecnt = 0
open_close_up = []
open_close_equal = []
open_close_down = []
for i in range(N):
  s = readline().rstrip()
  while "()" in s:
    s = s.replace("()","")
  opn = s.count("(")
  clo = s.count(")")
  if opn == 0 and clo == 0:
    # 空文字になったので無視してよい
    continue
  if opn == 0:
    # 全てクローズの場合
    closecnt += clo
  elif clo == 0:
    # 全てオープンの場合
    opencnt += opn
  elif opn > clo: # ")(("のようなケース
    open_close_up.append([clo,opn])
  elif opn == clo:
    open_close_equal.append([clo,opn])
  elif opn < clo:
    open_close_down.append([clo,opn])

open_close_up = sorted(open_close_up,key = lambda x:x[0]) # closeの数が少ない順
open_close_down = sorted(open_close_down,key = lambda x:x[0],reverse = True) # 多い順
  
# まずオープンを全て使う
cur = opencnt

# オープンの数が増えるものを全て使う
for i in range(len(open_close_up)):
  clo,opn = open_close_up[i][0],open_close_up[i][1]
  if clo > cur:
    print("No")
    exit(0)
  cur -= clo
  cur += opn

# オープンの数が変わらないものを全て使う
for i in range(len(open_close_equal)):
  clo,opn = open_close_equal[i][0],open_close_equal[i][1]
  if clo > cur:
    print("No")
    exit(0)
    
for i in range(len(open_close_down)):
  clo,opn = open_close_down[i][0],open_close_down[i][1]
  if clo > cur:
    print("No")
    exit(0)
  cur -= clo
  cur += opn
  
if cur - closecnt == 0:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
n = int(input())
S = [input() for i in range(n)]
AB = []
for i in range(n):
    a, b = 0, 0
    for c in S[i]:
        if c == '(':
            b += 1
        if c == ')':
            if b > 0:
                b -= 1
            else:
                a += 1
    AB.append((a, b))
AB0 = [(a, b) for a, b in AB if -a + b >= 0]
AB1 = [(a, b) for a, b in AB if -a + b < 0]
AB0.sort()
AB1.sort(key=lambda x: -x[1])
AB = AB0 + AB1
x = 0
for a, b in AB:
    x -= a
    if x < 0:
        print('No')
        exit()
    x += b
if x == 0:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
css = [0] * N
mns = [0] * N
t = [x for x in range(N)]
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(": css[x] += 1
    if S[i] == ")":
      css[x] -= 1
      mns[x] = min(mns[x], css[x])
if sum(css):
  print("No")
  exit(0)
t.sort(key = lambda x: -10 ** 7 if mns[x] == 0 else -10 ** 7 - mns[x] if css[x] >= 0 else mns[x] - css[x])
l = 0
for i in t:
  if l + mns[i] < 0:
    print("No")
    exit(0)
  l += css[i]
print("Yes")

Submission status: Accepted

Solution code:
n = int(input())
lst_left = []
lst_right = []
total = 0
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b-h, -h))
  total += h
#lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
#lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)

if total != 0:
  print("No")
  exit()
h = 0
for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
h = 0
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
print("Yes")

Submission status: Accepted

Solution code:
n=int(input())
L=0
R=0

p1=[]
p2=[]
p3=[]

for _ in range(n):

    s=input()

    #パターン１：))((
    #パターン２：))　右に置きたいタイプ
    #パターン３：（（左に置きたいタイプ

    flag=0
    ll=0
    rr=0
    temp=0

    for ss in s:
        if ss==")":
            if  rr>0:
                rr-=1
            else:
                ll+=1
        elif ss=="(":
            rr+=1
 #   print(s,rr,ll)
    if rr>0 and ll>0:
        p1.append((ll-rr,ll,rr))
    elif rr>0:
        p3.append(rr)
    else:
        p2.append(ll)

cnt=0
for item in p3:
    cnt+=item

#print(p1,p2,p3)

p1.sort()
for item in p1:
    lll=item[1]
    rrr=item[2]

    cnt-=lll
    if cnt<0:
        print("No")
        exit()
    cnt+=rrr

    if cnt<0:
        print("No")
        exit()

for item in p2:
    cnt-=item
    if cnt<0:
        print("No")
        exit()
if cnt==0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    sys.exit()
st=[[t[i]] for i in range(n)]

for i in range(n):
    now,mi=0,0
    for j in s[i]:
        if j=="(":
            now+=1
        else:
            now-=1
        mi=min(mi,now)
    st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
    if i<lu:
        now2+=u[i][0]
    elif i<lu+lv:
        if now2+v[i-lu][1]<0:
            print("No")
            break
        now2+=v[i-lu][0]
    else:
        #いや、間違ってるのここなんかーーい
        if now2+w[i-lu-lv][1]<0:
            print("No")
            break
        now2+=w[i-lu-lv][0]
else:
    print("Yes")

Submission status: Accepted

Solution code:
n,inc,dec=int(input()),[],[]
for _ in range(n):
  s,d,r=input(),0,0
  for c in s:
    d=d+(1 if c=='(' else -1)
    r=max(r,-d)
  (dec if d<0 else inc).append((d,r))
inc.sort(key=lambda x:x[1])
dec.sort(key=lambda x:x[0]+x[1])
p1,p2,ok=0,0,True
for s in inc:
  ok&=s[1]<=p1
  p1+=s[0]
for s in dec:
  ok&=p2>=s[0]+s[1]
  p2-=s[0]
ok&=p1==p2
print('Yes'if ok else'No')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input().rstrip() for _ in range(N)]

    neg = []
    pos = []
    total = 0
    for i, s in enumerate(S):
        t = 0
        tmn = 0
        for c in s:
            if c == '(':
                t += 1
            else:
                t -= 1
            tmn = min(tmn, t)
        if t >= 0:
            pos.append((tmn, t))
        else:
            neg.append((tmn - t, -t))
        total += t

    if total != 0:
        print('No')
        return
    t = 0
    for tmn, tsm in sorted(pos, reverse=True, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    t = 0
    for tmn, tsm in sorted(neg, reverse=True, key=lambda x: x[0]):
        if t + tmn < 0:
            print('No')
            return
        t += tsm
    print('Yes')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n = int(input())
x, y = [], []
for _i in range(n):
    s = input()
    p = 0
    m = [0]
    for j in range(len(s)):
        if s[j]=="(":
            p += 1
        else:
            p -= 1
            m.append(p)
    if p > 0:
        x.append([min(m), p])
    else:
        y.append([min(m)-p, -p])

x.sort(reverse=True)
y.sort(reverse=True)
r = 0
for s, t in x:
    if r+s < 0:
        print("No")
        sys.exit()
    r += t
result = 0
for s, t in y:
    if result+s < 0:
        print("No")
        sys.exit()
    result += t
if r-result == 0:
    print("Yes")
else:
    print("No")