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: Wrong Answer

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]:
            print('No')
            exit()
        else:
            used[i] = True
            s += A[i][1]
            count += 1
            if count == N:
                flag = True
                break
    if flag:
        break
    
print('Yes')

Submission status: Wrong Answer

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

for i, x in enumerate(S):
    res = []
    q = 0
    for y in x:
        if y == ')':
            if q > 0:
                q -= 1
            else:
                res.append(y)
        else:
            q += 1
    res += ['(']*q
    S[i] = list(res)
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)):
        if x[j] == '(':
            tmp += 1
        else:
            tmp -= 1
        m[i] = min(tmp, m[i])
    s[i] = tmp

if sum(s) == 0:
    ss = [(S[i], m[i]) for i in range(N)]
    ss.sort(key=lambda x: x[1], reverse=True)
    tmp = 0
    for x, y in ss:
        for z in x:
            if z == '(':
                tmp += 1
            else:
                tmp -= 1
                if tmp < 0:
                    print("No")
                    exit(0)
    print("Yes")

else:
    print("No")

Submission status: Wrong Answer

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:
#     pl.sort()
# if ql:
#     ql.sort()
# if ml:
#     ml.sort()
# if pl:
#     if pl[0][0]==')':
#         print('No')
#         exit()
# else:
#     if ml[0][0]==')':
#         print('No')
#         exit()

# if ql:
#     if ql[-1][-1]=='(':
#         print('No')
#         exit()
# else:
#     if ml[-1][-1]=='(':
#         print('No')
#         exit()


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])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a
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
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a

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])
    d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a

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])
    #d=0
    for a,b in pp:
        if d<a:
            print('No')
            exit()
        d+=b-a


print('Yes')

Submission status: Wrong Answer

Solution code:
from itertools import combinations

import numpy as np


def run():
    n = int(input())
    s_list = [input() for _ in range(n)]
    s_list = np.array([encode(s) for s in s_list])

    s = np.sum(s_list, axis=0)

    s_list_is_0 = s_list == 0

    left_found = (s_list_is_0 == np.array([True, False])).all(axis=1)
    right_found = (s_list_is_0 == np.array([False, True])).all(axis=1)

    if s[0] == s[1] == 0:
        print('Yes')
    elif s[0] == s[1] and left_found.any() and right_found.any():
        print('Yes')
    else:
        print('No')


def encode(s: str):
    temp_s = s
    while True:
        next_s = temp_s.replace('()', '')
        if temp_s == next_s:
            break
        temp_s = next_s

    return temp_s.count(')'), temp_s.count('(')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.n = 2**(len(arr) - 1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i - 1] = arr[i]
        for i in range(self.n - 1)[::-1]:
            self.tree[i] = func(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def set(self, idx, x):
        idx += self.n - 1
        self.tree[idx] = x
        while idx:
            idx = (idx - 1) // 2
            self.tree[idx] = self.func(self.tree[2 * idx + 1], self.tree[2 * idx + 2])

    def query(self, lt, rt):
        if rt <= lt:
            return self.ie
        lt += self.n - 1
        rt += self.n - 2
        tmp_l = self.ie
        tmp_r = self.ie
        while rt - lt > 1:
            if lt & 1 == 0:
                tmp_l = self.func(tmp_l, self.tree[lt])
            if rt & 1 == 1:
                tmp_r = self.func(self.tree[rt], tmp_r)
                rt -= 1
            lt = lt // 2
            rt = (rt - 1) // 2
        if lt == rt:
            tmp_l = self.func(tmp_l, self.tree[lt])
        else:
            tmp_l = self.func(self.func(tmp_l, self.tree[lt]), self.tree[rt])
        return self.func(tmp_l, tmp_r)

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)

import sys
input = sys.stdin.readline

from bisect import bisect_left, bisect_right

INF = 10**18

N = int(input())
S = [input().rstrip() for _ in range(N)]
if N % 2 == 0:
    S.append('()')
    N += 1

D = []

for i in range(N):
    kakko = 0
    minkakko = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            kakko += 1
        else:
            kakko -= 1
        minkakko = min(kakko, minkakko)
    D.append((minkakko, kakko))

D.sort()
E = []

for i in range(N):
    E.append(D[i][0])


F = []
for i in range(N):
    F.append((D[i][1], i))

s = 0

st = SegmentTree(F, max, (-INF, 0))

for i in range(N):
    x = bisect_left(E, -s)

    if x >= N:

        print('No')
        break
    v = st.query(x, N + 1)
    if v[0] == -INF:
        print('No')

        break
    s += v[0]
    st.set(v[1], (-INF, v[1]))
    if s < 0:
        print('No')
        break
else:
    if s == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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 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()

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

Submission status: Wrong Answer

Solution code:
N = int(input())
sum = 0
Max = 0
M = 0
for i in range(N):
    S = input()
    m = 0
    n = 0
    t = 0
    for s in S:
        if s == "(":
            t += 1
        else:
            t -= 1
        if m >= t:
            m = t
        if n <= t:
            n = t
    if m == 0:
        M += t
    else:
        M0 = min(M,sum+m)
        M1 = max(Max+m,M0)
        M = min(M1,M+t)
    sum += t
    if Max <= sum:
        Max = sum
if sum != 0 or M < 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    tp = 0 
    tm = []
    left = 0
    right = 0
    for i in range(N):
        S = input()
        w = 0
        wl = 0
        l = 0
        r = 0
        for j in S:
            if j == '(':
                l += 1
                wl += 1
            else:
                r += 1
                w -= 1
                w += wl
                wl = 0
        left += l
        right += r
        if w >= 0:
            tp += (l - r)
        else:
            tm.append((l - r, -w))
    if left != right:
        return False
    tm.sort(key=lambda x: x[1])
    while tm:
        tmp = []
        for i in tm:
            if i[1] <= tp:
                tp += i[0]
                if tp < 0:
                    return False
            else:
                tmp.append(i)
        if len(tmp) == len(tm):
            return False
        tm = tmp
    return True
if main():
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
N=int(input())

slist=[]
for _ in range(N):
  s=input()
  while True:
    s_new=s.replace("()","")
    #print(s,s_new)
    if s_new==s:
      s=s_new
      break
    else:
      s=s_new
  slist.append(s)
#print(slist)

rl_list=[]
for i in range(N):
  s=slist[i]
  l=s.count("(")
  r=s.count(")")
  if l>0 or r>0:
    rl_list.append((l-r,l,r))
rl_list.sort(reverse=True)
#print(rl_list)
  
lsum=rsum=0
lmin=rmin=float("inf")
l0max=r0max=0
for lr,r,l in rl_list:
  rsum+=r
  lsum+=l
  lmin=min(lmin,l)
  rmin=min(rmin,r)
  if l==0:
    l0max=max(l0max,r)
  if r==0:
    r0max=max(r0max,l)
  
if rsum!=lsum:
  print("No")
elif rmin>0 or lmin>0:
  print("No")
else:
  #print(l0max,r0max)
  if r0max>=rl_list[0][1]:
    print("Yes")
  else:
    print("No")

Submission status: Wrong Answer

Solution code:
def RunLengthEncoding(S):
    res = []
    N = len(S)
    i = 0
    while i < N:
        cnt = 1
        while i < N - 1 and S[i] == S[i + 1]:
            cnt += 1
            i += 1
        res.append([S[i], cnt])
        i += 1

    while True:
        res2 = omit(res)
        if res == res2:
            return res2
        res = res2


def omit(RLE):
    res = []
    i = 0
    while i < len(RLE):
        k, v = RLE[i]
        if k == ")":
            res.append([k, v])
            i += 1
            continue
        if i >= len(RLE) - 1:
            res.append([k, v])
            break

        kk, y = RLE[i + 1]
        if v > min(v, y):
            res.append([k, v - min(v, y)])
        if y > min(v, y):
            res.append([kk, y - min(v, y)])
        i += 2
    if res:
        res = merge(res)
    return res


def merge(RLE):
    res = []
    res.append(RLE[0])
    for i in range(1, len(RLE)):
        k, v = RLE[i]
        if res[-1][0] != k:
            res.append([k, v])
        else:
            res[-1][1] += v
    return res


if __name__ == "__main__":
    N = int(input())
    tmp = []
    for _ in range(N):
        RLE = RunLengthEncoding(input())
        if RLE:
            tmp.append(RLE)

    if not tmp:
        print("Yes")
        exit()

    outR = 0
    outL = 0
    LR = []
    for b in tmp:
        if len(b) == 1:
            k, v = b[0]
            if k == "(":
                outR += v
            else:
                outL += v
        else:
            _, v1 = b[0]
            _, v2 = b[1]
            LR.append((v1, -v2))

    LR.sort()
    x = outR
    y = outL
    for l, r in LR:
        if outR < l:
            print("No")
            exit()
        outR = outR - l - r
        x -= r
        y += l

    if x != y:
        print("No")
        exit()

    if outR == outL:
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

left = 0
right = 0

has_z_left = False
has_z_right = False
has_sep = False
ZERO = 0

for _ in range(N):
    S = list(input())
    L = len(S)

    r = 0
    l = 0
    for i in range(L):
        s = S[i]

        if s == ")":
            if l == 0:
                r += 1
            else:
                l -= 1
        elif s == "(":
            l += 1

    R = r

    r = 0
    l = 0
    for i in range(L - 1, -1, -1):
        s = S[i]

        if s == "(":
            if r == 0:
                l += 1
            else:
                r -= 1
        elif s == ")":
            r += 1

    L = l

    if L == 0 and R > 0:
        has_z_left = True

    if R == 0 and L > 0:
        has_z_right = True

    if L == 0 and R == 0:
        ZERO += 1

    if not (L == R and L == 0):
        has_sep = True

    left += L
    right += R


if left == right:
    if not has_sep:
        print("Yes")
    else:
        if (has_z_left and has_z_right) or 2 <= ZERO:
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
ls = [0] * N
rs = [0] * N
t = 0
for x in range(N):
  S = list(input())[: -1]
  for i in range(len(S)):
    if S[i] == "(":
      t += 1
      rs[x] += 1
    if S[i] == ")":
      t -= 1
      if rs[x]: rs[x] -= 1
      else: ls[x] += 1
"""
if t:
  print("No")
  exit(0)"""
if sum(ls) == 0:
  print("Yes")
  exit(0)
l = 0
r = 0
for i in range(N):
  if ls[i] == 0 and (rs[i] > 0): l = 1
  if rs[i] == 0 and (ls[i] > 0): r = 1
if l & r:
  print("Yes")
else: print("No")

Submission status: Wrong Answer

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


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

    nl = 0
    nr = 0

    buff_l = 0
    buff_r = 0

    for _ in range(N):
        S = input()
        for s in S:
            if s == '(':
                buff_l += 1
            elif s == ')':
                if buff_l > 0:
                    buff_l -= 1
                else:
                    buff_r += 1

        if buff_l == buff_r == 0:
            continue

        if buff_l > buff_r:
            nl += max(buff_l - nr, 0)
            nr = max(nr - buff_l, 0)
        elif buff_r > buff_l:
            nr += max(buff_r - nl, 0)
            nl = max(nl - buff_r, 0)
        else:
            if nr > nl:  # left
                nl += max(buff_l - nr, 0)
                nr = max(nr - buff_l, 0) + buff_r
            else:
                nr += max(buff_r - nl, 0)
                nl = max(nl - buff_r, 0) + buff_l

        buff_l = 0
        buff_r = 0

    if nr == nl == 0:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    
    need = [(0,0)]
    dif = 0
    
    for _ in range(N):
        S = input()
        l,r = 0,0
        for st in S:
            if st == "(":
                l += 1
            else:
                if l > 0:
                    l -= 1
                else:
                    r += 1
        if l == r:
            dif = max(dif,l)
        else:
            need.append((l,r))
            
    i,j = dif,dif
    for x,y in need:
        if x == 0:
            i -= y
        else:
            j -= x
            
    if i == j and i <= 0:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

n=int(input())
S=[]
for i in range(n):
    s=input()
    count=0
    mins=0
    for j in range(len(s)):
        if s[j]=='(':
            count+=1
        elif s[j]==')':
            count-=1
            if count<mins:
                mins=count
    S.append([mins*-1,count])
    
S.sort()
print(S)

count=0
flag=True

for i in range(n):
    if count>=S[i][1]:
        count+=S[i][0]
    else:
        flag=False
        break

if flag and count==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
brackets = []
def change(S):
    left = 0
    right = 0
    cnt = 0
    SUM = 0
    for i in S:
        if i == '(':
            left += 1
            SUM += 1
        else:
            if left > 0:
                left -= 1
                cnt += 1
            right += 1
            SUM += 1
            
    return (right - cnt, -1 * (SUM - right - cnt))

for _ in range(N):
    brackets.append(change(input()))

B = []
cnt = 0
for b in brackets:
    if b[0] == 0:
        cnt -= b[1]
    else:
        B.append([-b[1]-b[0], b[0], b[1]])

B.sort(reverse = True)

for b in B:
    cnt -= b[1]
    if cnt < 0:
        print('No')
        sys.exit()
    cnt -= b[2]

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

Submission status: Wrong Answer

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

A = [0 for i in range(N)]

for i in range(N):
    a = 0
    b = 0
    c = 0
    for j in range(len(S[i])):
        if S[i][j] == '(':
            a += 1
            c = min(a - b, b)
        else:
            b += 1
            c = min(a - b, b)
    A[i] = (a-b,c)

from operator import itemgetter

sorted(A,key = itemgetter(1),reverse = True)


d = 0
e = 0

for i in range(N):
    if -e > A[i][1]:
        print('No')
        exit()
    else:
        d += A[i][0]
        e += A[i][0]
else:
    if d == 0 and e == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())
a = 0
aa = 0
b = 0
c = 0
d = 0
e = 0
for i in range (N):
    S = input()
    a += S.count('(')
    aa += len(S)-a
    if S[0] == ')' and S[-1] == ')':
        b += 1
    elif S[0] == '(' and S[-1] == ')':
        c += 1
    elif S[0] == ')' and S[-1] == '(':
        d += 1
    elif S[0] == '(' and S[-1] == '(':
        e += 1

if a == aa and b == e:
    if d >= 1:
        if b >= 1:
            print('Yes')
        else:
            print('No')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
def count(s):
    ret = 0
    max_down = 0
    for c in s:
        if c=="(": ret += 1
        else: ret -= 1
        max_down = min(max_down,ret)
    return max_down, ret

n = int(input())
s_count_plus = []
s_count_minus = []
for i in range(n):
    si = input()
    down, num = count(si)
    if num >= 0:
        s_count_plus.append((down, num))
    else:
        s_count_minus.append((num, down))

s_count_plus.sort(reverse=True)
s_count_minus.sort(reverse=True)

ans = "No"
count_sum = 0

flag = 1

for down, num in s_count_plus:
    if count_sum + down < 0:
        flag = 0
        break
    count_sum += num

for num, down in s_count_minus:
    if count_sum + down < 0:
        flag = 0
        break
    count_sum += num

if flag and count_sum == 0: ans = "Yes"

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

INF = 10 ** 18

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

T = []
for s in S:
    a, b = 0, 0
    for ss in s:
        if ss == ")":
            if a:
                a -= 1
            else:
                b += 1
        else:
            a += 1
    T.append([a, b])
#print(T)

ta, tb = 0, 0
for t1, t2 in T:
    ta += t1
    tb += t2
#print(ta, tb)

if ta != tb:
    print("No")
    exit()

A = []
B = []
C = []

for i in range(N):
    if T[i][1] == 0:
        A.append(T[i])
    else:
        if T[i][0] >= T[i][1]:
            B.append(T[i])
        else:
            C.append(T[i] + [T[i][1] - T[i][0]])
#print(A, B, C)
B.sort(key = lambda x: x[1])
C.sort(key = lambda x: x[2])

cnt = 0
for a in A:
    cnt += a[0]
#print(cnt)

for b in B:
    cnt -= b[0]
    if cnt < 0:
        print("No")
        exit()
    cnt += b[1]

for c in C:
    cnt -= c[0]
    if cnt < 0:
        print("No")
        exit()
    cnt += c[1]

print("Yes")

Submission status: Wrong Answer

Solution code:
def multi(ar,al,br,bl):
  return ar + max(br-al,0), bl + max(al-br,0)

N = int(input())
suml1 = 0
suml2 =0
sumr1 = 0
sumr2 = 0
for i in range(N):
  bufl = 0
  bufr = 0
  for s in input():
    if s=="(":
      bufl += 1
    elif s==")":
      if bufl > 0:
        bufl -= 1
      else:
        bufr += 1
  if bufl == 0 or bufr==0:
    suml1 += bufl
    sumr1 += bufr
  else:
    if min(sumr2,bufl) > min(suml2,bufr):
      sumr2, suml2 = multi(bufr,bufl,sumr2,suml2)
    else:
      sumr2, suml2 = multi(sumr2,suml2,bufr,bufl)
summ = suml1 + suml2 - sumr1 -sumr2
if summ==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
import random
cnt1=0
cnt2=0
for inp in range(n):
    s=input()
    cnt1+=s.count("(")
    cnt2+=len(s)

if cnt1*2!=cnt2:
    print("No")
else:
    if random.random()>0.7:
        res="No"
    else:
        res="Yes"
    print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = [input() for _ in range(N)]
L = []
start = False
end = False
left_sum = 0
right_sum = 0

good_left_sum = 0
good_right_sum = 0
normal_left_sum = 0
normal_right_sum = 0
max_block = 0

for i in S:
    l_join = 0
    r_join = 0
    for j in i:
        if j == '(':
            r_join += 1
        else:
            if r_join > 0:
                r_join -= 1
            else:
                l_join += 1
    if r_join == 0 and l_join == 0:
        continue
    left_sum += l_join
    right_sum += r_join
    if r_join == 0:
        end = True
        good_left_sum += l_join
    elif l_join == 0:
        start = True
        good_right_sum += r_join
    elif r_join == l_join:
        max_block = max(max_block, r_join)
    elif r_join > l_join:
        normal_right_sum += r_join - l_join
    elif r_join < l_join:
        normal_left_sum += l_join - r_join
    # L.append((l_join, r_join))
# print(L)
# print(start)
# print(end)
if not((left_sum == right_sum) and start and end):
    print('No')
    exit()
if (normal_right_sum + good_right_sum >= max_block) and (normal_left_sum + good_left_sum >= max_block):
    print('Yes')
else:
    print('No')