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: Runtime Error

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

N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append([mim, end])
  else:
    S_n.append([end-mim, end])
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

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

Submission status: Runtime Error

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


import numpy as np
N = int(input())
S = [parse(input()) for _ in range(N)]
#a[0]+a[1]が大きい順に並べる
S.sort(key=lambda a: -a[0] - a[1])
#この中でa[1]が耐えられるものを貪欲にかき集める
#集められなくなったら終了


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


def f(x, y):
    return y if y[2] + cnt >= 0 else x


cnt = 0
ti = (10**10, 0, -10**10)
st = SegmentTree([(i, a[0], a[1]) for i, a in enumerate(S)], f=f, ti=ti)
for _ in range(N):
    x = st.query(0, N)
    if x[2] + cnt < 0:
        No()
    cnt += x[1] + x[2]
    st.update(x[0], ti)
if cnt == 0:
    Yes()
else:
    No()

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

A=list(map(int,input().split()))
n=len(A)
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0]
    slup.sort(key = lambda x: -x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 or h+si[0] < 0::
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[1])
    slmiddle = [si for si in sl if si[i] >= 0 and si[0] < 0]
    slmiddle.sort(key = lambda x: x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in slmiddle:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    slup = [si for si in sl if si[1] >= 0 and s[0] >= 0]
    sldown = [si for si in sl if si[1] < 0 or s[0] < 0]
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    print(sldown)
    for si in sldown[::-1]:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

def is_bracket_string(str):
  dir = 0
  for c in str:
    dir +=  ( -1  if c == '(' else +1 )
    if 0 < dir:
      return False
  return (dir == 0)

def check_all(strs):
  targets = []
  dirs = []
  for s in strs:
    dir = len(s) - 2 * s.count('(')
    if dir != 0 or not is_bracket_string(s):
      targets.append(s)
      dirs.append(dir)

  if sum(dirs) != 0:
    return False

  if len(targets) == 1:
    return False

  sorted_strs = [ s for (dir, s) in sorted(zip(dirs, targets), key=lambda x:x[0]) ]
  cat_str = ''.join(sorted_strs)
  return is_bracket_string(cat_str)


#
#
n, = map(int, input())

strs = []
for i in range(0, n):
  s = input()
  strs.append(s)

if check_all(strs):
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

Solution code:
#from collections import defaultdict, deque
#import itertools
#import numpy as np
#import re

def main():
    N = int(input())
    SS = []
    for _ in range(N):
        SS.append(input())
    S = []
    for s in SS:
        while '()' in s:
            s = s.replace('()', '')
        S.append(s)
    #print(S)
    S = [s for s in S if s != '']
    sum_op = 0
    sum_cl = 0
    S_both_op = []
    S_both_cl = []
    for s in S:
        if not ')' in s:
            sum_op += len(s)
        elif not '(' in s:
            sum_cl += len(s)
        else:
            pos = s.find('(')
            if pos <= len(s) - pos:
                S_both_op.append((pos, len(s)-pos))  #closeのほうが少ない、'))((('など -> (2,3)
            else:
                S_both_cl.append((pos, len(s)-pos))  #closeのほうが多い、')))(('など -> (3,2)

    # S_both_opは、耐えられる中でより伸ばす順にしたほうがいい？
    sort(S_both_op, key=lambda x: x[0])  #closeの数が小さい順にsort
    sort(S_both_cl, key=lambda x: x[0])  #これもcloseの数が小さい順にsort

    for p in S_both_op:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    for p in S_both_cl:
        sum_op -= p[0]
        if(sum_op < 0 ):
            print('No')
            exit()
        sum_op += p[1]
    
    if sum_op == sum_cl:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

# process
l1 = []
l2 = []
for s in S:
    i=0
    a = 0
    b = 0
    while i < len(s) and s[i] == ')':
        a += 1
        i += 1
    while i < len(s):
        if s[i] == '(':
            b += 1
        else:
            b -= 1
        i += 1
    
    if a+b != 0:
        if a <= b:
            l1.append((a, b))
        else:
            l2.append((b, a))

l1.sort()
l2.sort(reverse=True)

result = False
x = 0
if l1[0][0] == 0 and l2[-1][0] == 0:
    for a, b in l1:
        x += b-a
    for b, a in l2:
        x += b-a

    if x == 0:
        result = True

# output
print("Yes" if result else "No")

Submission status: Runtime Error

Solution code:
import sys

input = lambda : sys.stdin.readline

# 入力
N = int(input())

S1 = [] # 増えるシーケンス用
S2 = [] # 減るシーケンス用

# 入力その２
for i in range(N):

    S = input()  # シーケンス
    mid, end = 0, 0    

    for s in S:
        if s == '(':
            end += 1
        else:
            end -= 1
            
        mid = min(mid, end)  # 途中経過で一番減るところを探す

    if end > 0:
        S1.append((mid, end))
    else:
        S2.append((mid-end, -end))

S1.sort(reverse=True)
# S2.sort(key = lambda x : (x[0], -x[1]))
S2.sort(reverse=True)


mid = end1 = 0  # スタート
out = False

for t in S1:
    a, b = t
    mid = end1 + a
    end1 = end1 + b
    if mid < 0 or end1 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break

mid = end2 = 0  # スタート
for t in S2:
    a, b = t
    mid = end2 + a
    end2 = end2 + b
    if mid < 0 or end2 < 0:  # 途中で左カッコの数が右を上回る
        out = True
        break
        
if (not end1 == end2) or out:  # 右、左 の数が合わない
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
from itertools import permutations

n = int(input())
s = []
for _ in range(n):
	subseq = input()
	left = 0
	right = 0
	for char in subseq:
		if char == "(":
			left = 0
		else:
			right = 0
	s.append(left - right)

for perm in permutations(s):
	foo = 0
	for num in perm:
		foo += num
		if foo < 0:
			break
	else:
		if foo = 0:
			print ("Yes")
			break
else:
	print ("No")

Submission status: Runtime Error

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    while a!=b:
        b=a
        a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

x=limit

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

limit=s2
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s5[i][1]+s5[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0 and len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1

if flag==0 and x==limit:
    print("Yes")
elif flag==0:
    print("No")

Submission status: Runtime Error

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1

if len(s3)!=0:
    for i in range(len(s3)):
        if limit>=s3[i][0]:
            limit=limit-s3[i][0]+s3[i][1]
        else:
            flag=1
            print("No")
            break

if len(s4)!=0:
    if limit<max(s4):
        print("No")
        flag=1
    
if len(s5)!=0:    
    if flag==0:
        for i in range(len(s5)):
            if limit>=s5[i][1]:
                limit=limit-s3[i][1]+s3[i][0]
            else:
                flag=1
                print("No")
                break

if flag==0:
    print("Yes")

Submission status: Runtime Error

Solution code:
n=int(input())
s1=0
s2=0
s3=list()
s4=list()
s5=list()
for i in range(n):
    a=str(input())
    a=a.replace(r'()','')
    if len(a)==0:
        continue
    if a[0]=="(" and a[-1]=="(":
        s1+=len(a)
    elif a[0]==")" and a[-1]==")":
        s2+=len(a)
    else:
        x=len(a.replace("(",""))
        y=len(a)-x
        if x<=y:
            s3.append([x,y])
        elif x==y:
            s4.append(x)
        else:
            s5.append([x,y])
            
s3.sort(key=lambda x:x[0])
s5.sort(key=lambda x:x[1])

flag=0
limit=s1
for i in range(len(s3)):
    if limit>=s3[i][0]:
        limit=limit-s3[i][0]+s3[i][1]
    else:
        flag=1
        print("No")
        break

if limit<max(s4):
    print("No")
    flag=1
    
if flag==0:
    for i in range(len(s5)):
        if limit>=s5[i][1]:
            limit=limit-s3[i][1]+s3[i][0]
        else:
            flag=1
            print("No")
            break

if flag==0:
    print("Yes")

Submission status: Runtime Error

Solution code:
N = int(input())
pl = []
mi = []

for i in range(N):
    _m = 0
    _t = 0
    s = input()
    for c in s:
        if c == ")":
            _t -= 1
            _m = min(_m, _t)
        else:
            _t += 1
    if _t > 0:
        pl.append([_m, -_t]) # sortの調整のために負にしている
        # totalは大きい順
        # mは小さい順
    else:
        mi.append([_m, - _t])
pl = sorted(pl)
mi = sorted(mi)

import IPython;IPython.embed()


if len(pl) == 0:
    if mi[0][0] == 0:
        print("Yes")
    else:
        print("No")
    exit()
if len(mi) == 0:
    print("No")
    exit()

tot = 0
for m, nt in pl:
    if tot + m < 0:
        print("No")
        exit()
    else:
        tot += nt
for m, nt in mi:
    if tot + m <0:
        print("No")
        exit()
    else:
        tot -= nt
if tot != 0:
    print("No")
else:
    print("Yes")
        



# どういう時できるか
# で並べ方
# tot, minの情報が必要
# totが+のものはminとtotを気をつける必要がある
# minがsum以上であればどんどん足していけばいい.
# なのでminが小さい順にsortし,totの大きい順にsort
# その次はtotがminusの中ではminが小さい順に加える
# 合計が0になる時Yes,それ意外No.

Submission status: Runtime Error

Solution code:
n = int(input())
li = []

for _ in range(n):
    s = input()
    count = 0
    while True:
        if count + 1 >= len(s):
            break
        if s[count] == '(' and s[count+1] == ')':
            s = s[:count] + s[count+2:]
            count = max(0, count-1)
        else:
            count += 1
    li.append(s)

li2 = []
for i in li:
    count = 0
    for j in range(len(i)):
        if i[j] == ')':
            count += 1
        else:
            break
    li2.append((count, len(i) - count))

li3 = []
li4 = []

for i in li2:
    if i[0] <= i[1]:
        li3.append(i)
    else:
        li4.append(i)

li3.sort()
li4.sort(key = lambda x: x[1], reverse = True)

s2 = ''
for l,r in li3:
    s2 += ')' * l + '(' * r
for l,r in li4:
    s2 += ')' * l + '(' * r

count = 0
while True:
    if count + 1 >= len(s2):
        break
    if s2[count] == '(' and s2[count+1] == ')':
        s2 = s2[:count] + s2[count+2:]
        count = max(0, count-1)
    else:
        count += 1

if s2 == '':
    print('Yes')
else:

Submission status: Runtime Error

Solution code:
N = int(input())
pl = []
mi = []

for i in range(N):
    _m = 0
    _t = 0
    s = input()
    for c in s:
        if c == ")":
            _t -= 1
            _m = min(_m, _t)
        else:
            _t += 1
    if _t > 0:
        pl.append([- _m, _t]) # sortの調整のために負にしている
    else:
        mi.append([_m, - _t])
pl = sorted(pl)
mi = sorted(mi)

import IPython;IPython.embed()


if len(pl) == 0:
    if mi[0][0] == 0:
        print("Yes")
    else:
        print("No")
    exit()
if len(mi) == 0:
    print("No")
    exit()

tot = 0
for m, nt in pl:
    if tot - m < 0:
        print("No")
        exit()
    else:
        tot += nt
for m, nt in mi:
    if tot + m <0:
        print("No")
        exit()
    else:
        tot -= nt
if tot != 0:
    print("No")
else:
    print("Yes")
        



# どういう時できるか
# で並べ方
# tot, minの情報が必要
# totが+のものはminとtotを気をつける必要がある
# minがsum以上であればどんどん足していけばいい.
# なのでminが小さい順にsortし,totの大きい順にsort
# その次はtotがminusの中ではminが小さい順に加える
# 合計が0になる時Yes,それ意外No.

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Part:

    def __init__(self, string):
        self.slope, self.floor = self.calc_slope_floor(string)

    def __repr__(self):
        return "s{} f{}".format(self.slope, self.floor)

    def __lt__(self, other):
        if self.floor > self.other:
            return True
        if self.slope > self.slope:
            return True
        return False

    @staticmethod
    def calc_slope_floor(string):
        slope = 0
        floor = 0
        for c in string:
            if c == '(':
                slope += 1
            else:
                slope -= 1
            floor = min(floor, slope)
        return slope, floor

    def flip(self):
        self.slope *= -1
        self.floor += self.slope

    def catenate(self, other):
        assert(self.slope >= 0)
        if self.slope < abs(other.floor):
            return False
        self.slope += other.floor
        # self.floor is not needed

def sum_slope(parts):
    s = 0
    for p in parts:
        s += p.slope
    return s

def calc_flat_floor(flat):
    floor = 0
    for f in flat:
        floor = min(floor, f.floor)
    return floor

def enable(parts):
    parts = sorted(parts)
    #print('parts') # debug
    #print(parts) # debug
    chain = Part("")
    for p in parts:
        flg = chain.catenate(p)
        if flg == False:
            return False
    return True



def solve(up, down, flat):
    up_slope = sum_slope(up)
    down_slope = sum_slope(down)
    if up_slope != down_slope:
        return False
    flat_floor = calc_flat_floor(flat)
    #print('up_slope') # debug
    #print(up_slope) # debug
    #print('flat_floor') # debug
    #print(flat_floor) # debug
    if up_slope < abs(flat_floor):
        return False
    if not enable(up):
        return False
    if not enable(down):
        return False
    return True


if __name__ == '__main__':
    n = int(input())
    up = []
    down = []
    flat = []
    for _ in range(n):
        s = input()
        p = Part(s)
        if p.slope > 0:
            up.append(p)
        elif p.slope < 0:
            p.flip()
            down.append(p)
        else:
            flat.append(p)
    ans = solve(up, down, flat)
    if ans:
        print("Yes")
    else:
        print("No")


    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
def result(m, b):
    sum1 = m
    resmin = m
    for i in range(len(b)):
        resmin += b[i][0]
        if resmin < 0:
            return -1
        else:
            resmin += b[i][1] - b[i][0]
    for i in range(len(b)):
        sum1 += b[i][1]
    if sum1 != 0:
        return -1
    return 0
fin = open('input.txt', 'r')
n = int(fin.readline().strip('\n'))
resmin = 10 ** 7
set_pos = []
set_neg = []
for i in range(n):
    a = fin.readline().strip('\n')
    loc_min = 10 ** 7
    total = 0
    flag = True
    tmp = 0
    for j in range(len(a)):
        if a[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < loc_min:
            loc_min = tmp
    total = tmp
    if total >= 0:
        set_pos.append((loc_min, total))
    else:
        set_neg.append((loc_min, total))
total_pos = 0
set_pos = sorted(set_pos, key = lambda l: l[0], reverse = True)
for elem in set_pos:
    if total_pos + elem[0] < 0:
        flag = False
    total_pos += elem[1]   
b = sorted(set_neg, key = lambda l: l[1] - l[0], reverse = True)
#print(b)
print(set_pos, b)
res = result(total_pos, b)
print('No' if (res == -1 or not flag) else 'Yes')

Submission status: Runtime Error

Solution code:

up_list = []
down_list = []

for _ in range(n):
    txt = input()
    min_comp = 10 ** 6
    compare = 0
    cnt = 0
    for s in txt:
        cnt += 1
        if s == '(':
            compare += 1
        else:
            compare -= 1
            min_comp = min(min_comp, compare)
    if compare > 0:
        up_list.append([compare, min(min_comp, 0)])
    else:
        down_list.append([compare, min(min_comp, 0) - compare])


up_list.sort(key=lambda x: x[1], reverse=True)
down_list.sort(key=lambda x: x[1], reverse=False)
txt = 'No'
c = 0

for t in up_list + down_list:
    if t[1] + c < 0:
        break
    else:
        c += t[0]
else:
    if c == 0:
        txt = 'Yes'

print(txt)

Submission status: Runtime Error

Solution code:
import sys
N = int(f.input())
S = [str(f.input()) for _ in range(N)]

plus_stock = []
minus_stock = []
for i, row in enumerate(S):
    lowest = 0
    now = 0
    for j,char in enumerate(row):
        if char == "(":
            now+=1
        elif char == ")":
            now-=1 
        if now < lowest:
            lowest = now
    if now >= 0:
        plus_stock.append([now, lowest])
    else:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1])
minus_stock = sorted(minus_stock, key = lambda x:x[1])

now = 0

for i in range(len(plus_stock)):
    if now + plus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+plus_stock[i][0]
last = now
now = 0
for i in range(len(minus_stock)):
    if now + minus_stock[i][1] < 0:
        print("No")
        sys.exit()
    else:
        now = now+minus_stock[i][0]
if last == now:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

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


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

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

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

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        height = 0
        bottom = 0
        for c in s:
            if c == "(":
                height += 1
            else:
                height -= 1
                bottom = min(bottom, height)
        if height > 0:
            up_lines.append((bottom, height))
        else:
            down_lines.append((bottom-height, -height))
    up_lines.sort(reverse=True, key=lambda line: line.bottom)
    down_lines.sort(reverse=True, key=lambda line: line.bottom)
    left = 0
    for bottom, height in up_lines:
        if left + bottom < 0:
            print("No")
            return
        left += height
    right = 0
    for bottom, height in down_lines:
        if right + bottom < 0:
            print("No")
            return
        right += height
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
po,ne=[],[]
now=0
for i in range(n):
    p=0
    mp=0
    for j in input():
        p+=(1,-1)[j==")"]
        mp=min(p,mp)
    if mp:
        if p>=0:
            po.append((mp,p))
        else:ne.append((mp-p,-p))
    else:now+=p
po.sort(reverse=1)
ne.sort(reevrse=1)
for m,p in po+ne:
    if m+now<0:print("No");exit()
    else:now+=p
print("No") if now else print("Yes")

Submission status: Runtime Error

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)
    se=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
            se.add(m)
            stack[m].append(p-m)
            l_PM[p-m].append(m)
    
    for x in se:
        stack[x].sort()
        y=stack[x].pop()
        Seg.update(x,y)
    
    for _ in range(c):
        x=Seg.query(0,P+1)
        if x==-INF:
            print('No')
            exit()
        if P+x<0:
            print('No')
            exit()
        
        l_PM[x].sort()
        
        index=l_PM[x][bisect_left(l_PM[x],P)]
        if stack[index]:
            y=stack[index].pop()
            Seg.update(index,y)
        else:
            Seg.update(index,-INF)
        P+=x
    P-=M
    YesNo(P==0)

if __name__ == '__main__':
    main()