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:
def ques():
    n=input()
    open=0
    close=0
    lis=[]
    for _ in range(int(n)):
        co=0
        cc=0
        t=input()
        for i in t:
            if i=="(":
                co+=1
            if i==")":
                if co>=1:
                    co-=1
                else:
                    cc+=1
        if (co,cc)!=(0,0):
            lis.append((cc,co))
    # print(lis)
    if not lis:
        print("Yes")
        return
    lis.sort()
    curr_open=0
    i=0
    while(lis[i][0]==0):
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("No")
        return
    while(i<len(lis) and curr_open>0):
        curr_open-=lis[i][0]
        if curr_open<0:
            print("No")
            return
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("Yes")
    else:
        print("No")
ques()

Submission status: Runtime Error

Solution code:
def ques():
    n=input()
    open=0
    close=0
    lis=[]
    for _ in range(int(n)):
        co=0
        cc=0
        t=input()
        for i in t:
            if i=="(":
                co+=1
            if i==")":
                if co>=1:
                    co-=1
                else:
                    cc+=1
        if (co,cc)!=(0,0):
            lis.append((cc,co))
    # print(lis)
    lis.sort()
    curr_open=0
    i=0
    while(lis[i][0]==0):
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("No")
        return
    while(i<len(lis) and curr_open>0):
        curr_open-=lis[i][0]
        if curr_open<0:
            print("No")
            return
        curr_open+=lis[i][1]
        i+=1
    if curr_open==0:
        print("Yes")
    else:
        print("No")
ques()

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0][X]=1
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in dp[n+1]:
                        dp[n][X]=1
                        nstack.append([n+1,xl,xr])
        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0]
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in dp[n+1]:
                        dp[n+1]=X
                        nstack.append([n+1,xl,xr])
        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    N, M, K = map(int, input().split())
    const = 998244353

    ans = 0
    col = M

    for k in range(N - 1, -1, -1):
        now = col * comb(N - 1, k)
        if k <= K:
            ans += now
        col *= (M - 1)

    print(ans % const)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
if not lr:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

idleR=10**7
if lr:
    L,R=lr[0]
    dp=[defaultdict(int) for i in range(len(lr))]
    X=L+idleR*R
    dp[0]
    stack=[[0,L,R]]
    while stack:
        n,l,r=stack.pop()
        if n+1<len(lr):
            L,R=lr[n+1]
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in dp[n+1]:
                        visited.add(X)
                        nstack.append([xl,xr])
        else:
            if l<=rlst:
                L=rlst-l
            else:
                continue
            if r<=llst:
                R=llst-r
            else:
                continue
            if L-R==0:
                print("Yes")
                exit()



print("No")

Submission status: Runtime Error

Solution code:


n = 0
s = []

def format_input(filename = None):
	global n
	global s
	if filename == None:
		n = int(input())
		s = [str(input()) for i in range(n)]

	elif filename == '__random__':
		from random import randint as rng
		from random import choices
		n = rng(1, 10**6)
		l = [rng(0, 10**6 - n) for i in range(n)]
		l.append(0)
		l.sort()
		s = [''.join(choices('()', k = l[i+1] - l[i] + 1)) for i in range(n)]
		print(n)
		[print(i) for i in s]

def semi_blacket(s):
	left, right = [0] * 2
	if len(s) == 0:
		return left, right

	l, r = semi_blacket(s[1:])
	if s[0] == '(':
		if l == 0:
			right = r + 1
		else:
			left = l - 1
			right = r
	else:
		left = l + 1
		right = r

	return left, right

def get_answer():
	answer = 'No'
	left = [0] * n
	right = [0] * n
	l_close, r_close = False, False
	for i in range(n):
		left[i], right[i] = semi_blacket(s[i])
		if left[i] == 0:
			l_close = True
		elif right[i] == 0:
			r_close = True

	if sum(left) == sum(right) and (l_close and (r_close or right.count(0) > 1)):
		answer = 'Yes'
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
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
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = 998244353


n = I()
m = SR(n)
A = []
L = 0
R = 0
for b in m:
    l = 0
    r = 0
    m = deque()
    flg = 0
    for a in b:
        if m and m[-1] == '(' and a == ')':
            m.pop()
            r -= 1
        elif a == '(':
            m += ['(']
            r += 1
        else:
            l += 1
    A += [(l, r, r - l)]
    L += l
    R += r


class Segtree:
    def __init__(self, A, ide_ele, segfunc, initialize=True):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        if initialize:
            self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
            for i in range(self.size - 1, 0, -1):
                self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.size)

    def update(self, k, x):
        k += self.size
        self.data[k] = x
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

if L != R:
    print('No')
else:
    A.sort()
    seg = Segtree([(INF, INF, INF) for i in range(n)], (INF, INF, INF), min)
    ret = 0
    res = 0
    idx = -1
    for i in range(n):
        while idx < n and A[idx + 1][0] <= res:
            idx += 1
            seg.update(idx, A[idx])
        q, ql, qr = seg.query(0, ret + 1)
        if q == INF:
            print('No')
            exit()
        ret += q
        res = max(res, ret)
    print('Yes')

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele for _ in range(2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

Min = []
Now = []
c = 0
Snow = 0

for i in range(N):
    s = rl().rstrip()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        elif j == ')':
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    
    if minimum<0:
        Min.append(minimum)
        Now.append([now, c])
        c += 1
    else:
        Snow += now
    #A.append([minimum,now])

#print(Min)
#print(Now)
#print(A)
# zipで二つの配列を統合
zipped = zip(Min, Now)
# 統合していた配列をもとに戻す
Min, Now = zip(*sorted(zipped))
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**15
ide_ele = [-INF,-INF]
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = Snow

#print(Min)
#print(Now)
#print(Seg.seg)

LL = len(Now)

for _ in range(LL):
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    if i==LL:
        print('No')
        sys.exit()
    j,k = Seg.query(i, LL)
    
    #print(j)
    if k == -INF:
        print('No')
        sys.exit()

    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()

print('Yes')

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele for _ in range(2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

Min = []
Now = []
c = 0
Snow = 0

for i in range(N):
    s = rl().rstrip()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        elif j == ')':
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    
    if minimum<0:
        Min.append(minimum)
        Now.append([now, c])
        c += 1
    else:
        Snow += now
    #A.append([minimum,now])

#print(Min)
#print(Now)
#print(A)
# zipで二つの配列を統合
c = zip(Min, Now)
# 統合していた配列をもとに戻す
Min, Now = zip(*sorted(c))
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**15
ide_ele = [-INF,-INF]
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = Snow

#print(Min)
#print(Now)
#print(Seg.seg)

LL = len(Now)

for _ in range(LL):
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    if i==LL:
        print('No')
        sys.exit()
    j,k = Seg.query(i, LL)
    
    #print(j)
    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()

print('Yes')

Submission status: Runtime Error

Solution code:


n = 0
s = []

def format_input(filename = None):
	global n
	global s
	if filename == None:
		n = int(input())
		s = [str(input()) for i in range(n)]

	elif filename == '__random__':
		from random import randint as rng
		from random import choices
		n = rng(1, 10**6)
		l = [rng(0, 10**6 - n) for i in range(n)]
		l.append(0)
		l.sort()
		s = [''.join(choices('()', k = l[i+1] - l[i] + 1)) for i in range(n)]
		print(n)
		[print(i) for i in s]

def semi_blacket(s):
	left, right = [0] * 2
	if len(s) == 0:
		return left, right

	l, r = semi_blacket(s[1:])
	if s[0] == '(':
		if l == 0:
			right = r + 1
		else:
			left = l - 1
			right = r
	else:
		left = l + 1
		right = r

	return left, right

def get_answer():
	answer = 'No'
	left = [0] * n
	right = [0] * n
	l_close, r_close = False, False
	for i in range(n):
		left[i], right[i] = semi_blacket(s[i])
		if left[i] == 0:
			l_close = True
		elif right[i] == 0:
			r_close = True

	if sum(left) == sum(right) and l_close and r_close:
		answer = 'Yes'
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
llst=[]
lr=[]
rlst=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    if l and not r:
        llst.append(l)
    elif not l and r:
        rlst.append(r)
    elif l or r:
        lr.append([l,r])
llst=sum(llst)
rlst=sum(rlst)

if not llst and not rlst and not lr:
    print("Yes")
    exit()
stack=[]
idleR=10**7
if lr:
    L,R=lr[0]
    stack=[[L,R]]
    for n in range(1,len(lr)):
        #print(stack)
        L,R=lr[n]
        visited=set()
        nstack=[]
        while stack:
            l,r=stack.pop()
            for xl,xr in [[l+L-R,r],[l,r+R-L]]:
                if xl>=0 and xr>=0:
                    X=xl+idleR*xr
                    if not X in visited:
                        visited.add(X)
                        nstack.append([xl,xr])
if not stack:
    if llst-rlst==0:
        print("Yes")
    else:
        print("No")
    exit()

for l,r in stack:
    print(Unko)
    if l<=rlst:

        L=rlst-l
        l=0
    else:
        continue
    if r<=llst:

        R=llst-r
        r=0
    else:
        continue

    if L-R==0:
        print("Yes")
        exit()
    else:
        continue
print("No")

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele for _ in range(2*self.num)]
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline

N = Int()
Sum = 0

Min = []
Now = []
c = 0
Snow = 0

for i in range(N):
    s = rl().rstrip()
    now = 0
    minimum = 0
    for j in s:
        if j=='(':
            now += 1
        elif j == ')':
            now -= 1
        minimum = min(minimum,now)
    Sum += now
    
    if minimum<0:
        Min.append(minimum)
        Now.append([now, c])
        c += 1
    else:
        Snow += now
    #A.append([minimum,now])

#print(Min)
#print(Now)
#print(Now2)
#print(A)
# zipで二つの配列を統合
c = zip(Min, Now)
# 統合していた配列をもとに戻す
Min, Now = zip(*sorted(c))
    
if Sum!=0:
    print('No')
    sys.exit()

INF = 10**15
ide_ele = [-INF,-INF]
Seg = SegTree(Now,ide_ele,max)

import bisect

count = 0
now = Snow

#print(Min)
#print(Now)

LL = len(Now)

for _ in range(LL):
    i = bisect.bisect_left(Min,-now)
    #print(i,N)
    j,k = Seg.query(i, LL)
    
    #print(j)
    now += j
    Seg.update(k,[-INF,k])
    
    if now<0:
        print('No')
        sys.exit()

print('Yes')

Submission status: Runtime Error

Solution code:
import numpy as np



n = int(input())
s = []
s_num = np.zeros(n)
s_num_min = np.zeros(n)
for i in range(n):
    kakko_in = input()
    s.append(kakko_in)
    for s_in in kakko_in:
        if s_in == '(':
            s_num[i] += 1
        else:
            s_num[i] -= 1
        if s_num[i] < s_num_min[i]:
            s_num_min[i] = s_num[i]

if np.sum(s_num) != 0:
    print("No")
else:
    now_sum = 0
    now_min_sum = 0
    s_num_index = s_num.argsort()[::-1]
    s_num_min_index = s_num_min.argsort()[::-1]
    # print(s_num_index)
    # print(s_num_min_index)
    yet = [1 for _ in range(n)]


    def nap(i1, i2, yet, now_sum):
        bool1 = 0
        bool2 = 0
        if sum(yet) == 0:
            return 1
        if i1 < n:
            i01 = s_num_index[i1]
            if yet[i01] and now_sum+s_num[i01] >= 0 and now_sum+s_num_min[i01] >= 0:
                yet[i01] = 0
                bool1 = nap(i1+1, i2, yet, now_sum+s_num[i01])
                yet[i01] = 1
        if i2 != i1 and bool1 == 0 and i2 < n:
            i02 = s_num_min_index[i2]
            if yet[i02] and now_sum+s_num[i02] >= 0 and now_sum+s_num_min[i02] >= 0:
                yet[i02] = 0
                bool2 = nap(i1, i2+1, yet, now_sum+s_num[i02])
                yet[i02] = 1
        # print(i1, i2, bool1, bool2)
        if bool1 + bool2 == 1:
            return 1
        else:
            return 0


    if nap(0, 0, yet, 0):
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

Solution code:
import heapq
import sys

#input = sys.stdin.readline

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

    data = [0]*N
    for i in range(N):
        S = list(str(input()))
        s = 0
        m = 0
        for j in range(len(S)):
            if S[j] == "(":
                s += 1
            else:
                s -= 1
                m = min(m,s)
        data[i] = (-m,-s)


    heapq.heapify(data)
    x = 0
    valid = []
    heapq.heapify(valid)

    det = 0

###
#print("data",data)
#print("valid",valid)
#print(x)
###

    while data or valid:
        while data and x - data[0][0] >= 0:
            y = heapq.heappop(data)
            heapq.heappush(valid,(y[1],y[0]))
    
        while valid and x >= 0:
            z = heapq.heappop(valid)
            if x - z[0] >= 0:
                x -= z[0]
            else:
                heappush(valid,z)
    
        if data and x - data[0][0] < 0:
            det = -1
            break

    if det == 0 and x == 0:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

if len(base3) > 0:
    1/0

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

for p,i,j in base3:
    if current < i:
        print("No")
        1/0
        exit()
    current -= i
    current += j
    
print("Yes")

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n=n_in()

base=[]

for _ in range(n):
    s = s_in()

    c = s[0]
    cnt = 1
    ar = []
    for t in range(1,len(s)):
        if s[t-1] == s[t]:
            cnt += 1
        else:
            ar.append((c,cnt))
            c = s[t]
            cnt = 1
    ar.append((c,cnt))

    start = 0
    if ar[0][0] == ")":
        start = 1

    r = 0 # ( の数
    sgn = 1
    for c,cnt in ar[start:]:
        r += sgn*cnt
        sgn *= -1


    res = ()
    if ar[0][0] == ")":
        if r >= 0:
            res = (ar[0][1], r)
        else:
            res = (ar[0][1]-r,0)
    else:
        if r >= 0:
            res = (0, r)
        else:
            res = (r, 0)

    base.append(res)

i_cnt = 0
j_cnt = 0

base2 = []

for i,j in base:
    i_cnt += i
    j_cnt += j

    if j > 0:
        base2.append((i,-(j-i),j))

if i_cnt != j_cnt:
    print("No")
    exit()

base2.sort()

current = 0


for i,p,j in sorted(filter(lambda x: x[1] <= 0 ,base2)):
    if current < i:
        print("No")
        1/0
        exit()
    current -= i
    current += j

base3 = []
for i,p,j in filter(lambda x: x[1] > 0 ,base2):
    base3.append((p,i,j))

base3.sort()

for p,i,j in base3:
    if current < i:
        print("No")
        exit()
    current -= i
    current += j
    
print("Yes")

Submission status: Runtime Error

Solution code:
N=int(input())
l=[]
flags=0
flagg=0
flag1s=0
flag1g=0
count=0
for i in range(N):
  a=input()
  A=[]
  for i in a:
    A.append(str(i))
    if i=="(":
      count+=1
    else:
      count-=1
  if flags==0:
    if A[0]=="(":
      flags=1
  elif flags==1:
    if A[len(A)]==")":
      flagg=1
  if flag1s==0:
    if A[0]=="(":
      flag1s=1
  elif flag1s==1:
    if A[len(A)]==")":
      flag1g=1
if ((flags==1 and flagg==1) or (flag1s==1 and flag1g==1)) and count==0:
  print("Yes")
else:
  print("No")