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
from itertools import permutations
readline = sys.stdin.readline

n = int(readline())
s = [readline().strip() for i in range(n)]

comb_s = list(permutations(s, n))

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    r = x.count('(')
    l = x.count(')')
    if r != l: return 0

    return 1

def main():
    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = [input() for i in range(N)]
S = [[0]*len(s[i]) for i in range(N)]
for i, x in enumerate(s):
    res = []
    q = 0
    for j in range(len(x)):
        if x[j] == ')':
            S[i][j] = -1
        else:
            S[i][j] = 1
s = [0]*N
m = [len(S[i]) for i in range(N)]
for i, x in enumerate(S):
    tmp = 0
    for j in range(len(x)):
        tmp += S[i][j]
        m[i] = min(tmp, m[i])
    s[i] = tmp

if sum(s) == 0:
    sp = [(m[i], s[i]) for i in range(N) if s[i] > 0]
    mp = [(-(s[i]-m[i]), -s[i]) for i in range(N) if s[i] <= 0]#右から見た場合
    sp.sort(key=lambda x: x[0], reverse=True)
    tmp = 0
    for x, y in sp:
        if tmp + x < 0:
            print("No")
            exit(0)
        tmp += y
    mp.sort(key=lambda x: x[0], reverse=True)
    tmp2 = 0
    for x, y in mp:
        if tmp2 + x < 0:
            print("No")
            exit(0)
        tmp2 += y
    print("Yes")

else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [input() for _ in range(n)]

def cap_right(s_):
    cap = 0
    stack = 0
    for x in s_[::-1]:
        if x == '(':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]

def cap_left(s_):
    cap = 0
    stack = 0
    for x in s_:
        if x == ')':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]

s_tuple_right = [cap_right(s_)+[idx] for idx,s_ in enumerate(s)]
#print(s_tuple_right)
s_tuple_right = list(filter(lambda x:x[0] == 0,s_tuple_right))
s_tuple_right.sort(key = (lambda x: x[1]),reverse=True)
if len(s_tuple_right) == 0:
    print("No")
    exit()
right_idx = s_tuple_right[0][2]
right_stack =  -s_tuple_right[0][1]
del s[right_idx]
s_tuple = [cap_left(s_) for s_ in s]
s_gain = list(filter(lambda x:x[1] > 0,s_tuple))
s_gain.sort(key = (lambda x: x[0]))
s_not_gain = list(filter(lambda x:x[1] <= 0,s_tuple))
s_not_gain.sort(key = (lambda x: x[0]),reverse=True)

score = 0
for s_ in s_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]
for s_ in s_not_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]
if score + right_stack == 0:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())

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

comb_s = list(itertools.permutations(s, len(s)))

def checker(x):
    jud = 1
    ans = ''.join(x)

    if not s:
        return jud

    r = x.count('(')
    l = x.count(')')
    if r != l:
        jud =0
        return jud

    if x[0] != '(' or x[-1] != ')':
        jud =0

    return jud

def main():
    for i in range(len(comb_s)):
        juds = checker(''.join( [j for j in comb_s[i]]))
        if juds == 1:
            print('Yes')
            return

    print('No')
    return
main()

Submission status: Time Limit Exceeded

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


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = []
for i in range(N):
    S.append(list(input()))

# ')' - '('
num = [0]*N
for i in range(N):
    val = 0
    temp = [0]*len(S[i])
    for j in range(len(S[i])):
        if S[i][j] == ')':
            temp[j] = temp[j-1]+1
        else:
            temp[j] = temp[j-1]-1

    num[i] = max(temp)

soukei = [0]*N
for i in range(N):
    temp = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            temp += 1
        else:
            temp -= 1
    soukei[i] = temp

if sum(soukei) != 0:
    print('No')
    exit()

A = []
for i in range(N):
    A.append((num[i],soukei[i]))

s = 0
used = [False]*N
count = 0
for i in range(N):
    if A[i][0] <= 0:
        used[i] = True
        s += A[i][1]
        count += 1

B = []
for i in range(N):
    if not used[i]:
        B.append(A[i])

B.sort(key=lambda x:(-x[1],x[0]))
flag = False
while True:
    for i in range(N):
        if used[i]:
            continue
        if s < A[i][0]:
            continue
        else:
            used[i] = True
            s += A[i][1]
            count += 1
            if count == N:
                flag = True
                break
    if flag:
        break
    
print('Yes')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur, cur - mn))

    tmp.sort(key=lambda x: (x[0], x[1]), reverse=True)
    #print(tmp)

    cur = 0
    idx = 0
    q = []
    count = 0
    while idx < N or len(q) > 0:
        while idx < N and cur + tmp[idx][0] >= 0:
            heapq.heappush(q, (-tmp[idx][2], -tmp[idx][1], -tmp[idx][0]))
            idx += 1
        if len(q) == 0:
            print(NO)
            return
        #print(count, q)
        diff, cnt, mn = heapq.heappop(q)
        diff, cnt, mn = -diff, -cnt, -mn
        #print(cnt, mn)
        if cur + mn < 0:
            print(NO)
            return
        cur += cnt
        count += 1

    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [input() for _ in range(n)]

pm = 0
for s_ in s:
    pm += s_.count('(') - s_.count(')')
if pm != 0:
    print("No")
    exit()

def cap_right(s_):
    cap = 0
    stack = 0
    for x in s_[::-1]:
        if x == '(':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]

def cap_left(s_):
    cap = 0
    stack = 0
    for x in s_:
        if x == ')':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]



s_tuple_right = [cap_right(s_)+[idx] for idx,s_ in enumerate(s)]
#print(s_tuple_right)
s_tuple_right = list(filter(lambda x:x[0] == 0,s_tuple_right))
s_tuple_right.sort(key = (lambda x: x[1]),reverse=True)
if len(s_tuple_right) == 0:
    print("No")
    exit()
right_idx = s_tuple_right[0][2]
del s[right_idx]
s_tuple = [cap_left(s_) for s_ in s]
s_gain = list(filter(lambda x:x[1] > 0,s_tuple))
s_gain.sort(key = (lambda x: x[0]))
s_not_gain = list(filter(lambda x:x[1] <= 0,s_tuple))
s_not_gain.sort(key = (lambda x: x[0]),reverse=True)

score = 0
for s_ in s_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]
for s_ in s_not_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]

print("Yes")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str
NO = "No"  # type: str

def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word

def solve(N: int):
    tokens = iterate_tokens()
    left_rights = deque([(0, 0)])
    left_all = 0
    right_all = 0
    for _ in range(N):

        #print("all", left_all, right_all)

        s = next(tokens)
        left = 0
        right = 0
        for ss in s:
            #print(ss)
            #print(left, right)
            if ss == ")":
                if right > 0:
                    right -= 1
                else:
                    left += 1
            else:
                right += 1

        # print(left, right)
        length = len(left_rights)
        for _ in range(length):
            left_right = left_rights.popleft()

            left_rights.append((max(0, left_right[0] - right) + left, max(0, right - left_right[0]) + left_right[1]))

            #print(new_left_all_right, new_right_all_right)

            left_rights.append((max(0, left_right[1] - left) + right, max(0, left - left_right[1]) + left_right[0]))

            #print(new_left_all_left, new_right_all_left)

    if (0, 0) in left_rights:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from itertools import permutations

def f(s):
    while True:
        t = s.replace('()', '')
        if t == s:
            return s
        s = t

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

l = 0
r = 0
for s in S:
    t = s.count('(')
    l += t
    r += len(s) - t
if l != r:
    print('No')
    exit()

S = [s for s in map(f, S) if s != ""]

if len(S) == 0:
    print('Yes')
    exit()

lS = [s for s in S if s[0] == "("]
rS = [s for s in S if s[0] == ")"]

ld = {}
for s in lS:
    ld.setdefault(s, 0)
    ld[s] += 1

rd = {}
for s in rS:
    rd.setdefault(s, 0)
    rd[s] += 1

for k1 in list(ld.keys()):
    k2 = k1[::-1]
    if k2 in rd:
        t = max(ld[k1], rd[k2])
        ld[k1] -= t
        rd[k2] -= t

if len(ld) == 0 and len(rd) == 0:
    print('Yes')
    exit()

SS = []
for k in ld:
    for i in range(ld[k]):
        SS.append(k)
for k in rd:
    for i in range(rd[k]):
        SS.append(k)

for ss in permutations(SS, len(SS)):
    t = reduce(lambda x, y: x + y, ss)
    if f(t) == '':
        print('Yes')
        exit()
print('No')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur, cur - mn))

    tmp.sort(key=lambda x: (x[0], x[1]), reverse=True)
    #print(tmp)

    cur = 0
    idx = 0
    q = []
    count = 0
    while count < N:
        while idx < N and cur + tmp[idx][0] >= 0:
            heapq.heappush(q, (-tmp[idx][2], -tmp[idx][1], -tmp[idx][0]))
            idx += 1
        if len(q) == 0:
            print(NO)
            return
        #print(count, q)
        diff, cnt, mn = heapq.heappop(q)
        diff, cnt, mn = -diff, -cnt, -mn
        #print(cnt, mn)
        if cur + mn < 0:
            print(NO)
            return
        cur += cnt
        count += 1

    #for mn, cnt, diff in tmp:
    #    if abs(mn) > cur:
    #        print(NO)
    #        return
    #    cur += cnt

    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


n = int(input())
minsum = [None] * n # (min, sum)
for i in range(n):
    tmp = list(map(int, " ".join(input()).replace("(", "1").replace(")", "-1").split()))
    c = 0
    m = 0
    for item in tmp:
        c += item
        m = min(c, m)
    minsum[i] = (m, sum(tmp))
minsum.sort()
if sum(item[1] for item in minsum)!=0:
    print("No")
else:
    c = 0
    i = n-1
    while minsum:
        m, s = minsum[i]
        if m<0:
            break
        c += s
        i -= 1
        minsum.pop()
    if not minsum:
        print("Yes")
    else:
        minsum.sort(key=lambda x: x[1])
    #     print(minsum, c)
        i = len(minsum)-1
        update = False
        while minsum:
            m, s = minsum[i]
            if c+m>=0:
                update = True
                minsum.pop(i)
                c += s
                i = len(minsum) - 1
            else:
                i -= 1
                if i<0 and not update:
                    print("No")
                    break
                else:
                    i = len(minsum) - 1
        else:
            print("Yes")

Submission status: Time Limit Exceeded

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


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close = 0

  for oreq, _, ocval, _ in values:
    if oreq > open_close:
      print('No')
      return

    open_close += ocval

  open_close = 0
  for _, creq, ocval, _ in values[::-1]:
    if creq > open_close:
      print('No')
      return

    open_close -= ocval

  print('Yes')


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
var = []
for n in range(N):
    var.append(input())
def T(data):
    tmp = data.replace("()","")
    for _ in range(len(tmp)//2):
        tmp = tmp.replace("()","")
    if tmp == "":
        print("Yes")
        exit()
    elif tmp == data:
        pass
    else:
        T(tmp)
    return
for temp in itertools.permutations(var,N):
    T("".join(temp))
print("No")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
left = []
right = []
last = None
for i in range(N):
	s = input()
	l = len(s)
	r_needed = 0
	l_needed = 0
	for j in range(l):
		if s[j] == "(":
			r_needed += 1
		elif s[j] == ")" and r_needed > 0:
			r_needed -= 1

		if s[l-1 - j] == ")":
			l_needed += 1
		elif s[l-1 - j] == "(" and l_needed > 0:
			l_needed -= 1
	if r_needed < l_needed:
		right.append((-r_needed, l_needed))
	else:
		left.append((l_needed, -r_needed))

left.sort()
right.sort()
rest_l = 0
for l in left:
	l_needed = l[0]
	r_needed = -l[1]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l += r_needed - l_needed
for r in right:
	l_needed = r[1]
	r_needed = -r[0]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l -= l_needed
	rest_l += r_needed
if rest_l != 0:
	print("No")
else:
	print("Yes")

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
left = []
right = []
for i in range(n):
    s = input()
    n0 = 0
    n1 = 0
    l = len(s)
    for j in range(l):
        if s[j] == "(":
            n0 += 1
        else:
            if n0 == 0:
                n1 += 1
            else:
                n0 -= 1
    if n0 > 0 or n1 > 0:
        if n0 >= n1:
            left.append([n1, n0])
        else:
            right.append([n0, n1])
 
left.sort()
right.sort()
 
def solve():
    nl0 = 0
    nl1 = 0
    for p in left:
        if p[0] > nl0:
            return False
        nl0 -= p[0]
        nl0 += p[1]
    nr0 = 0
    nr1 = 0
    for p in right:
        if p[0] > nr1:
            return False
        nr1 -= p[0]
        nr1 += p[1]
    if nl0 == nr1:
        return True
    else:
        return False
 
if solve():
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

Flag=False

for s in itertools.permutations(S,n):
    count=0
    flag=True
    for i in range(n):
        for j in range(len(s[i])):
            if s[i][j]=='(':
                count+=1
            elif s[i][j]==')':
                count-=1
                if count<0:
                    flag=False
                    break
    if flag and count==0:
        Flag=True
        break
if Flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools
import copy

class Simple:
    def __init__(self):
        self.memo = {}
    
    def simplify(self,s):
        try:
            return self.memo[s]
        except:
            tmp = copy.copy(s)
            while '()' in s:
                s=s.replace('()','')
            self.memo[tmp] = s
            return s


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    S_arr = []
    smpl = Simple()
    for i in range(N):
        _ =     _in[i+1]   # type:str
        _ = smpl.simplify(_)
        S_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    candidate = list(itertools.permutations(S_arr))
    for cand in candidate:
        s = ''.join(cand)
        if len(smpl.simplify(s))==0:
            TF = 'Yes'
            break
    else:
        TF = 'No'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
var = []
for n in range(N):
    var.append(input())
def T(data):
    tmp = data.replace("()","")
    if tmp == "":
        print("Yes")
        exit()
    elif tmp == data:
        pass
    else:
        T(tmp)
    return
for temp in itertools.permutations(var,N):
    T("".join(temp))
print("No")

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

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


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


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


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


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

Submission status: Time Limit Exceeded

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

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
for m,t in B:
    if totB + m < 0:
        ans = False
        break
    totB += t
if totA != totB:
    ans = False

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import itertools

def simplify(s):
    while '()' in s:
        s=s.replace('()','')
    return s


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    S_arr = []
    for i in range(N):
        _ =     _in[i+1]   # type:str
        _ = simplify(_)
        S_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    candidate = list(itertools.permutations(S_arr))
    for cand in candidate:
        s = ''.join(cand)
        if len(simplify(s))==0:
            TF = 'Yes'
            break
    else:
        TF = 'No'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(TF)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
sss = [input()[:-1] for _ in range(n)]

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


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


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


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


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

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
check = []
judge = False
right_count = 0
left_count = 0
for i in range(N):
  S = input()
  check.append(S)
for i in check:
  for j in i:
    if j == '(':
      left_count += 1
    elif j == ')':
      right_count += 1
right_count -= left_count
if right_count == 0:  
  for i in list(itertools.permutations(check)):
    if i[0][0] == '(' and i[len(i)-1][len(i[len(i)-1])-1] == ')':
      judge = True
    elif i[len(i)-1][len(i[len(i)-1])-1] == '(' and i[0][0] == ')':
      judge = True
    if judge:
      break
  if judge:
    print('Yes')
  else:
    print('No')
else:
  print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
n = int(input())
sss = [input()[:-1] for _ in range(n)]

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


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


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


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


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
bra = []
ket = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  bra.append([-mini,now])
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  ket.append([-mini,now])  
check = 0
for x in bra:
  #print(x)
  check += x[1]
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    tmp = heapq.heappop(pool)
    now -= tmp
    if tmp > 0:
      break

ket.sort()
now = 0
here = -1
#print(bra)
pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    tmp = heapq.heappop(pool)
    now -= tmp
    if tmp > 0:
      break
print('Yes')