Problem:


Score : 600 points

Problem Statement

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

An empty string;

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

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

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

Constraints

1 \leq N \leq 10^6

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

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

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

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

Sample Input 1

2
)
(()

Sample Output 1

Yes

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

Sample Input 2

2
)(
()

Sample Output 2

No

Sample Input 3

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

Sample Output 3

Yes

Sample Input 4

3
(((
)
)

Sample Output 4

No



Sample input:
2
)
(()


Sample output:
Yes

Submission status: Time Limit Exceeded

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

N = int(input())
S = [input().rstrip() for _ in range(N)]

A = []
B = []

for s in S:
    a = 0
    k = 0
    for i in range(len(s)):
        if s[i] == ')':
            k += 1
        else:
            k -= 1
        a = max(a, k)
    b = 0
    k = 0
    for i in range(len(s))[::-1]:
        if s[i] == '(':
            k += 1
        else:
            k -= 1
        b = max(b, k)
    A.append(a)
    B.append(b)

L = []
R = []

for i in range(N):
    if B[i] - A[i] >= 0:
        L.append((A[i], i))
    else:
        R.append((B[i], i))

L.sort()
R.sort(reverse=True)

T = ''

for a, i in L:
    T += S[i]

for b, i in R:
    T += S[i]

k = 0

for t in T:
    if t == '(':
        k += 1
    else:
        k -= 1
    if k < 0:
        print('No')
        break
else:
    if k == 0:
        print('Yes')
    else:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input().strip() for _ in range(N))
    print(solve(S))

class LRCount:
    def __init__(self):
        self.left_open = 0
        self.right_open = 0
    def __repr__(self):
        return str((self.left_open, self.right_open))
    def lrdiff(self):
        return self.left_open - self.right_open

def get_count(s):
    result = LRCount()
    cum_sum = 0
    for c in s:
        if c == ')':
            cum_sum -= 1
        else:
            cum_sum += 1
        result.left_open = max(result.left_open, -cum_sum)
    cum_sum = 0
    for c in s[::-1]:
        if c == '(':
            cum_sum -= 1
        else:
            cum_sum += 1
        result.right_open = max(result.right_open, -cum_sum)
    return result

def solve(S):
    counts = list(map(get_count, S))
    first_groups = sorted(filter(lambda c: c.lrdiff() <= 0, counts), key=lambda c: c.left_open)
    second_groups = sorted(filter(lambda c: c.lrdiff() > 0, counts), key=lambda c: -c.right_open)
    cum_sum = 0
    order = first_groups + second_groups
    cum_sum = 0
    for c in order:
        cum_sum -= c.left_open
        if cum_sum < 0:
            return 'No'
        cum_sum += c.right_open
    if cum_sum == 0:
        return 'Yes'
    return 'No'

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input().rstrip('\n'))
S = [str(input().rstrip('\n')) 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])
    elif now < 0:
        minus_stock.append([-now, lowest - now])
plus_stock  = sorted(plus_stock, key = lambda x:x[1], reverse=True)
minus_stock = sorted(minus_stock, key = lambda x:x[1], reverse=True)

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: Time Limit Exceeded

Solution code:
import itertools

if __name__ == '__main__':
    N = input()
    N = int(N)
    S = [0]*N
    for i in range(N):
        S[i] = input()

    s = []
    for v in itertools.permutations(S):
        s.append(v)

    s = list(set(s))
    s.sort()

    flag = False

    for i in range(len(s)):
        str = ''.join(s[i])
        while str.find("()") != -1:
            str = str.replace("()","")
        if str == "":
            flag = True
            break
        s[i] = str

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

if __name__ == '__main__':
    N = input()
    N = int(N)
    S = [0]*N
    for i in range(N):
        S[i] = input()

    s = []
    for v in itertools.permutations(S):
        s.append(v)



    for i in range(len(s)):
        str = ''.join(s[i])
        while str.find('()') != -1:
            str = str.replace('()','')
        s[i] = str

    s = list(set(s))

    s.sort()

    if len(s) == 2:
        print("Yes")
    else:
        print("No")

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

n = int(input())
s = []
for _ in range(n):
	s.append(input())
	
for perm in permutations(s):
	seq = "".join(perm)
	left = 0
	right = 0
	for char in seq:
		if char == "(":
			left += 1
		else:
			right += 1
		if right > left:
			break
	else:
		if left == right:
			print("Yes")
			break
else:
	print ("No")

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools


num = int(input())
S = []
for _ in range(num):
    S.append(input())


result = False
for i in itertools.permutations(S):
    checkedArray = list(''.join(i))
    if checkedArray[0] == ")": continue

    cost = 0
    for index, item in enumerate(checkedArray):
        if item == "(": cost += 1
        else: cost -= 1

        if cost < 0: break
        if cost == 0 and index == len(checkedArray) - 1:
            result = True
            break

    if result == True: break

print("Yes" if result == True else "No")

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

#num, blockPosition = map(int, input().split())
#num = int(input())
#costArray = list(map(int, input().split()))

num = int(input())
S = []
for _ in range(num):
    S.append(input())


result = False
for i in itertools.permutations(S):
    checkedArray = list(''.join(i))
    if checkedArray[0] == ")": continue

    cost = 0
    for index, item in enumerate(checkedArray):
        if item == "(": cost += 1
        else: cost -= 1

        if cost < 0: break
        if cost == 0 and index == len(checkedArray) - 1:
            result = True
            break

    if result == True: break

print("Yes" if result == True else "No")

Submission status: Time Limit Exceeded

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

T = [0]*N
M = [0]*N
for i in range(N):
    res = 0
    idx = 0
    s = S[i]
    l = len(s)
    m = 0
    while idx<l:
        if s[idx]==')':
            res -= 1
            m = min(res,m)
        else:
            res += 1
        idx += 1
    
    M[i] = m
    T[i] = res

Tp = []
Tn = []
for i in range(N):
    if T[i]>=0:
        Tp.append([M[i], T[i]])
    else:
        Tn.append([M[i]-T[i], -T[i]])

Tp.sort(reverse = True)
Tn.sort(reverse = True)
res = 0
for m,t in Tp:
    if res<-m:
        print('No')
        exit()
    res += t

resn = 0
for m,t in Tn:
    if resn<-m:
        print('No')
        exit()
    resn += t
if res==resn:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Up = []
Down = []
for _ in range(N):
    S = input()
    L = [0]
    for __ in range(len(S)):
        if S[__] == '(':
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
    las = L[-1]
    mi = min(L)
    if las > 0:
        Up.append((mi, las))
    else:
        Down.append((mi - las, mi, las))

Up.sort(reverse=True)
Down.sort()

now = 0
for i, j in Up:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
for _, i, j in Down:
    if now + i < 0:
        print('No')
        exit()
    else:
        now += j
if now == 0:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def solve():
    INF = float('inf')

    #idEle = -INF  # max
    idEle = (-INF, -INF, -1)  # max  ### maxのインデックスを取得するために、この形式にする
    def _binOpe(x, y):
        return x if x >= y else y  # max
    def makeSegTree(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        return data, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iA, A):
        iST = iA + numPow2
        data[iST] = A  # set
    #    data[iST] += A  # add
    def update(iA, A):
        _update1(iA, A)
        iST = iA + numPow2
        while iST > 1:
            iST >>= 1
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        L = iSt + numPow2
        R = iEn + numPow2
        ans = idEle
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans

    def sign(x):
        if x > 0:
            return 1
        elif x < 0:
            return -1
        else:
            return 0

    N = int(input())
    Sss = [input().rstrip() for _ in range(N)]

    Ts = []
    T0s = []
    for Ss in Sss:
        nums = [0] + [1 if S == '(' else -1 for S in Ss]
        nums = list(accumulate(nums))
        # x:最下点, y:終点との差
        x = min(nums)
        y = nums[-1] - x
        x, y = abs(x), abs(y)
        Ts.append((x, y))
        T0s.append(x)

    Ts.sort()
    T0s.sort()
    # [終点が正]を優先→[終点が負]の中では、[終点との差MAX]を選ぶ
    Us = [(sign(-x+y), y, i) for i, (x, y) in enumerate(Ts)]

    data, numPow2 = makeSegTree(N)
    setInit(Us)

    vNow = 0
    for _ in range(N):
        # 採用可能な範囲を求める
        iT0 = bisect_right(T0s, vNow)
        if iT0 == 0:
            return False
        # 範囲内のMAXのインデックスを求める
        sgn, y, i = getValue(0, iT0)
        if i == -1:
            return False
        # 現在値を更新する
        x = Ts[i][0]
        vNow += -x+y
        update(i, idEle)

    return vNow == 0


if solve():
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def kakko(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

plus = []
minus = []

for l, r in S:
    if l <= r:
        plus.append((l, r))
    else:
        minus.append((l, r))

plus.sort(key=lambda a: a[0])
minus.sort(key=lambda a: a[1], reverse=True)
M = 0
for l, r in (plus + minus):
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
for i in range(n):
    l.append(list(input()))

p=0
q=0
for i in range(n):
    for j in l[i]:
        if j=='(':
            p+=1
        else:
            q+=1
if p!=q:
    print('No')
    exit()
pl=[]
ql=[]
ml=[]
for i in range(n):
    a=l[i]
    p=0
    q=0
    for j in a:
        if j=='(':
            p+=1
        else:
            q+=1
    if p>q:
        pl.append(a)
    elif p<q:
        ql.append(a)
    else:
        ml.append(a)
if pl:
    pp=[]
    for i in pl:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b
if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in i:
            if j=='(':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    #pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    #d=0
    if not pl:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

if ql:
    pp=[]
    for i in ql:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

if ml:
    pp=[]
    for i in ml:
        d=0
        t=0
        for j in range(len(i)):
            if i[len(i)-1-j]==')':
                d+=1
            else:
                d-=1
            t=max(t,-d)
        pp.append([t,d])
    #pp.sort(key=lambda x: x[0]*(10**6)-x[1])
    if not ql:
        dd=0
    for a,b in pp:
        if dd<a:
            print('No')
            exit()
        dd+=b

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    sums = 0
    mins = 0
    for s in S:
        if s == '(':
            sums += 1
        else:
            sums -= 1
            mins = min(mins, sums)
    if sums >= 0:
        L.append((sums, mins))
    else:
        R.append((-sums, mins-sums))

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

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    len_S = len(S)
    L_d = 0
    L_min_d = 0
    R_d = 0
    R_min_d = 0
    for i in range(len_S):
        if S[i] == '(':
            L_d += 1
        else:
            L_d -= 1
            L_min_d = min(L_min_d, L_d)
        if S[len_S-i-1] == ')':
            R_d += 1
        else:
            R_d -= 1
            R_min_d = min(R_min_d, R_d)
    if L_d >= 0:
        L.append((L_d, L_min_d))
    else:
        R.append((R_d, R_min_d))

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

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

plus = []
minus = []

for l, r in S:
    if l <= r:
        plus.append((l, r))
    else:
        minus.append((l, r))

plus.sort(key=lambda a: a[0])
minus.sort(key=lambda a: a[1], reverse=True)
M = 0
for l, r in (plus + minus):
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0:
        OK = False

h = 0
for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
def encode(s):
    val = 0
    min_val = 0
    for c in s:
        if c == '(':
            val += 1
        else:
            val -= 1
            min_val = min(min_val, val)
    return [min_val, val]

def check(s):
    h = 0
    for p in s:
        b = h + p[0]
        if b < 0:
            return False
        h += p[1]
    return True


n = int(input())
ls = []
rs = []
l_total = 0
r_total = 0
for _ in range(n):
    si = encode(input())
    if si[1] > 0:
        ls.append(si)
        l_total += si[1]
    else:
        si[0] -= si[1]
        si[1] *= -1
        rs.append(si)
        r_total += si[1]
list.sort(ls, reverse=True)
list.sort(rs, reverse=True)
if check(ls) and check(rs) and l_total == r_total:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import itertools as itl

N = int(input())
S = [input() for x in range(N)]
A = "".join(S)
if len(A) % 2 != 0:
    print("No")
    exit()
S = list(itl.permutations(S))
for x in S:
    st = "".join(x)
    j = 0
    k = 0
    for y in st:
        if y == "(":
            j += 1
        elif y == ")":
            k += 1
    if j + k == len(st) and st[0] == "(" and st[-1] == ")":
        print("Yes")
        exit()
print("No")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
#import queue# queue,get(), queue.put()
def run():
    N = int(input())
    current = 0
    ways = []
    dic = {'(': 1, ')': -1}
    for _ in range(N):
        S = input()
        go = 0
        max_depth = 0
        for s in S:
            go += dic[s]
            max_depth = min(max_depth, go)
        if current + max_depth < 0:
            ways.append((go, max_depth))
        else:
            current += go

    ways = sorted(ways, key=lambda x:x[0], reverse=True)

    while ways:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                done = True
                if go < 0:
                    break
                current += go
                del ways[idx]
                break
        if not done:
            break

    ways = sorted(ways, key = lambda x:x[1])

    while ways and current >= 0:
        done = False
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                current += go
                del ways[idx]
                done = True
                break
        if not done:
            print('No')
            return None


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

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
cnt2 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
# G4.sort()
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += sum(L[1] for L in G3)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
cnt2 = 0
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        cnt2 += cnt
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])


G2.sort(reverse=True)
for L in G2:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]
G4.sort()
for L in G4:
    if cnt2 + L[0] < 0:
        print('No')
        exit()
    else:
        cnt2 += L[1]

cnt2 += sum(L[1] for L in G3)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

cnt = 0
cnt += sum(L[0] for L in G1)
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]

cnt += sum(L[1] for L in G3)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

# print(G1,G2,G3,G4)

cnt = 0
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
        
cnt += sum(L[0] for L in G3)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
SS = []
G1,G2,G3,G4 = [],[],[],[]
for _ in range(N):
    S = input()
    MIN = 0
    cnt = 0
    for s in list(S):
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        MIN = min(MIN,cnt)
    if MIN == 0 and cnt >= 0:
        G1.append([MIN,cnt])
    if MIN < 0 and cnt >= 0:
        G2.append([MIN,cnt])
    if MIN == cnt and cnt < 0:
        G3.append([MIN,cnt])
    if MIN < cnt and cnt < 0:
        G4.append([MIN,cnt])

# print(G1,G2,G3,G4)

cnt = 0
for L in G1:
    cnt += L[1]
G2.sort(reverse=True)
for L in G2:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
G4.sort()
for L in G4:
    if cnt + L[0] < 0:
        print('No')
        exit()
    else:
        cnt += L[1]
for L in G3:
    cnt += L[1]

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s=['' for _ in range(n)]
for i in range(n):
    s[i]=input()
#x=[[0,0] for _ in range(n)]
hp,hm=0,0
p=[]
m=[]
for i in range(n):
    t=s[i]
    lv=0
    mn=0
    for u in t:
        if u == '(':
            lv+=1
        elif u == ')':
            lv-=1
        mn=min(mn,lv)
    #x[i][0],x[i][1]=lv,mn
    if lv>=0:
        p.append([lv,mn])
        hp+=lv
    else:
        lv*=-1
        m.append([lv,mn+lv])
        hm+=lv
if hp!=hm:
    print('No')
    exit()
p.sort(key=lambda x: x[1],reverse=1)
m.sort(key=lambda x: x[1],reverse=1)
h=0
lv,mn=0,0
for a,b in p:
    lv+=a
    mn+=b
    if mn<0:
        print('No')
        exit()
    mn=lv
lv,mn=0,0
for a,b in m:
    lv+=a
    mn+=b
    if mn<0:
        print('No')
        exit()
    mn=lv
print('Yes')

#print(lv,mn)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
s=[list(input()) for i in range(n)]
L1=[]
L2=[]
ct1=0;ct2=0
for i in range(n):
  ct3=0
  l=[0]
  for j in range(len(s[i])):
    if s[i][j]=='(':
      ct1+=1
      ct3+=1
      l.append(ct3)
    else:
      ct2+=1
      ct3-=1
      l.append(ct3)
  if l[-1]>=0:
    L1.append((min(l),l[-1]))
  else:
    L2.append((min(l)-l[-1],-l[-1]))
if ct1!=ct2:
  print('No')
  sys.exit()

L1.sort()
L1.reverse()
ct4=0
for i in range(len(L1)):
  if ct4+L1[i][0]<0:
    print('No')
    sys.exit()
  ct4+=L1[i][1]

L2.sort()
L2.reverse()
ct5=0
for i in range(len(L2)):
  if ct5+L2[i][0]<0:
    print('No')
    sys.exit()
  ct5+=L2[i][1]

print('Yes')

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp[0] = -m
        temp[1] = (s.count("(")-s.count(")"))-m
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
S = [input().rstrip('\n') for _ in range(N)]
sum_list = [0] * N
min_list = [0] * N
all_sum = 0
for i in range(N):
    sum = 0
    min = 10**7
    for c in S[i]:
        sum += 1 if c == '(' else -1
        if c == ')' and sum < min:
            min = sum
    sum_list[i], min_list[i] = (sum, min)
    all_sum += sum
if all_sum != 0:
    print('No')
else:
    fin = False
    for p in permutations(range(N), N):
        sum = 0
        for i in p:
            if sum + min_list[i] < 0:
                break
            sum += sum_list[i]
        else:
            print('Yes')
            fin = True
            break
    if not fin:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
cnt=0
def check(a,b):
    global cnt
    for i in range(len(a)):
        cnt-=a[i][0]
        if cnt<0:
            return False
        cnt+=a[i][1]

    for i in range(len(b)):
        cnt-=b[i][0]
        if cnt<0:
            return False
        cnt+=b[i][1]
    if cnt==0:
        return True
    return False

a=[]
b=[]
for i in range(int(input())):
    s=stdin.readline().strip()
    #print(s)
    ans=''
    for j in range(len(s)):
        if s[j]=='(':
            ans+='('
        else:
            if len(ans)==0:
                ans+=')'
                continue
            if ans[-1]=='(':
                ans=ans[:-1]
            else:
                ans+=')'
    L=0
    for j in range(len(ans)):
        if ans[j]==')':
            L+=1
        else:
            break
    R=len(ans)-L
    if L<R:
        a.append((L,R))
    else:
        b.append((L,R))

    a.sort()
    b.sort(key=lambda x:x[1],reverse=True)
    #print(a,b)
if check(a,b):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
S = [input().rstrip('\n') for _ in range(N)]
sum_list = [0] * N
min_list = [0] * N
all_sum = 0
for i in range(N):
    sum = 0
    min = 10**6
    for c in S[i]:
        sum += 1 if c == '(' else -1
        if c == ')' and sum < min:
            min = sum
    sum_list[i], min_list[i] = (sum, min)
    all_sum += sum
if all_sum != 0:
    print('No')
else:
    fin = False
    for p in permutations(range(N), N):
        sum = 0
        for i in p:
            if sum + min_list[i] < 0:
                break
            sum += sum_list[i]
        else:
            print('Yes')
            fin = True
            break
    if not fin:
        print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input())
S = [input().rstrip('\n') for _ in range(N)]
sum_list = [0] * N
min_list = [0] * N
all_sum = 0
for i in range(N):
    sum = 0
    min = 1
    for c in S[i]:
        sum += 1 if c == '(' else -1
        if sum < min:
            min = sum
    sum_list[i], min_list[i] = (sum, min)
    all_sum += sum
if all_sum != 0:
    print('No')
else:
    fin = False
    for p in permutations(range(N), N):
        sum = 0
        for i in p:
            if sum + min_list[i] < 0:
                break
            sum += sum_list[i]
        else:
            print('Yes')
            fin = True
            break
    if not fin:
        print('No')