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:
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))
#print(rl_list)
  
lsum=rsum=0
lmin=rmin=float("inf")
for r,l in rl_list:
  rsum+=r
  lsum+=l
  lmin=min(lmin,l)
  rmin=min(rmin,r)
  
if rsum!=lsum:
  print("No")
elif rmin>0 or lmin>0:
  print("No")
else:
  print("Yes")

Submission status: Wrong Answer

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

bs = []
for si in s:
    li, ri = 0, 0
    for c in si:
        if c == '(':
            li += 1
        elif c == ')' and li == 0:
            ri += 1
        elif c == ')' and 0 < li:
            li -= 1
    bs.append((ri, -li))

bs.sort()
bra = 0
ans = "Yes"
for (ri, li) in bs:
    li *= -1
    bra -= ri
    if bra < 0:
        ans = "No"
        break
    bra += li
if bra != 0:
    ans = "No"
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
dl,dr,dm=0,0,0
f=0
m=10**6
for i,s in enumerate(S):
    l,r=0,0
    for c in s:
        if c=='(':
            l+=1
        else:
            if l>0:l-=1
            else: r+=1
    if l>0 and r>0:
        dm+=l-r
        m=min(m,r)
        f=1
    elif l>0:
        dl+=l
    elif r>0:
        dr-=r
print(['No','Yes'][dl+dr+dm==0 and (f==0 or dl>=m)])

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

N = int(input())
sum_left, sum_right, sum_maxdif, sum_dif = 0, 0, 0, 0
for i in range(N):
    S = input()
    left = 0
    right = 0
    maxdif = 0
    for c in S:
        if c=='(':
            left += 1
        else:
            right += 1
        maxdif = max(maxdif, right - left)
    sum_left += left
    sum_right += right
    sum_maxdif += maxdif
    sum_dif += max(left-right, 0)
if sum_left != sum_right:
    print('No')
elif sum_maxdif > sum_dif:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
def check(s):
    p = 0
    stock_q = 0
    for chr in s:
        if chr == '(':
            stock_q += 1
        else:
            if stock_q:
                stock_q -= 1
            else:
                p += 1

    q = 0
    stock_p = 0
    for chr in s[::-1]:
        if chr == ')':
            stock_p += 1
        else:
            if stock_p:
                stock_p -= 1
            else:
                q += 1
    return p, q  # p = 左側に ) が残っている, q = 右側に ( が残っている


n = int(input())
pq_list = []
sum_p = 0
sum_q = 0

for _ in range(n):
    s = input()
    p, q = check(s)
    sum_p += p
    sum_q += q
    pq_list.append((p, q))

if sum_p != sum_q:
    print('No')
    exit()

pq_list.sort(key=lambda x: sum(x))

residue_p, residue_q = pq_list.pop()

if not pq_list:
    print('No')
    exit()

for p, q in pq_list[::-1]:
    if p == q:
        continue

    if p > q:
        residue_q -= p - q

    else:
        residue_p -= q - p

if residue_p == residue_q == 0:
    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:
            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
                nr = max(nr - buff_l, 0) + buff_r
                nl += max(buff_l - nr, 0)
            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:


N=int(input())


cand=[]
right=[]
left=[]
for _ in range(N):
    moji=input()
    if moji.count(")")-moji.count("(")>=0:
        right.append(moji)
    else:
        left.append(moji)
mx_r=[]
for item in right:
    mx=10**9
    temp=0
    for moji in item:
        if moji=="(":
            temp+=1
        else:
            temp-=1
        #print(temp)
        mx=min(temp,mx)
    mx_r.append([mx,item])

mx_l=[]
for item in left:
    mi=-10**9
    temp=0
    for moji in item:
        #print(temp)
        if moji=="(":
            temp+=1
        else:
            temp-=1
        mi=max(temp,mi)
    mx_l.append([mi,item])

mx_l.sort(key=lambda x:x[0],reverse=True)
mx_r.sort(key=lambda x:x[0],reverse=True)

#print(mx_r,mx_l)    

ans=""
for item in mx_l:
    ans+=item[1]
for item in mx_r:
    ans+=item[1]
#print(ans)

temp=0
for item in ans:
    if item=="(":
        temp+=1
    else:
        temp-=1
    if temp<0:
        print("No")
        exit()
if temp==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

import collections
buf = collections.deque()

def solve(S):
    for s in S:
        if buf:
            if s == ')':
                if buf[0] == '(':
                    buf.popleft()
                else:
                    buf.appendleft(s)

            else:
                buf.appendleft(s)

        else:
            buf.appendleft(s)

    left, right = 0, 0
    while buf:
        if buf.popleft() == '(':
            left += 1
        else:
            right += 1

    return left, right

S = [input() for _ in range(N)]
S.sort()
S = ''.join(S)
left, right = solve(S)
if left == 0 and right == 0:
    print('Yes')
else:
    print('No')

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 = M1
    sum += t
    if Max <= sum:
        Max = sum
if sum != 0 or M < 0:
    print("No")
else:
    print("Yes")

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

print('Yes')

Submission status: Wrong Answer

Solution code:
N = int(input())

a = 0
b = 0

for i in range(N):
    S = input()
    a += S.count('(')
    b += S.count(')')

if a == b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[]
B=[]
c=0
for i in range(n):
  S=input()
  a=0
  b=0
  for j in range(len(S)):
    if S[j]=="(":
      a=a+1
    else:
      a=a-1
      if a<b:
        b=a
  if b==0:
    c=c+a
  else:
    A.append([-1*b,a])
A.sort()
f=0
for i in range(len(A)):
  if c-A[i][0]<0:
    f=1
  c=c+A[i][1]
if c!=0:
  f=1
if f==0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = [input() for i in range(n)]
for idx,s in enumerate(S):
  l,r = 0,0
  for i ,si in enumerate(s):
    if si == "(":
      r += 1
    elif si == ")" and r > 0:
      r -= 1
    else:
      l += 1
  S[idx] = (l,r)
lsum = rsum = 0
lzero = zeror = 0
for l,r in S:
  if l > 0 or r > 0:count += 1
  if l > 0 and r == 0:lzero += 1
  if r > 0 and l == 0:zeror += 1
  lsum += l
  rsum += r
if lsum == rsum and (count == 0 or (lzero and zeror)):
  print("Yes")
else:
  print("No")
# print(S)

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()
    
ta, tb = 0, 0
for t1, t2 in T:
    ta += t1
    tb += t2

for i in range(N):
    if T[i][1] == 0:
        T[i].append(-INF)
    else:
        T[i].append(T[i][1] - T[i][0])
T.sort(key = lambda x: x[2])
#print(T)

a, b = 0, 0
for i in range(N):
    a -= T[i][1]
    if a < 0:
        print("No")
        exit()
    a += T[i][0]
print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 必要条件
# 1. ()の個数が等しくなければいけない
# 2.
#

# ()の個数が等しいのに成り立たない例
# (()(,)))( ←こういうときは成り立たない
# 一番で(とかになっちゃうやつがいると死ぬ
# 中に何個()が存在するかも考慮しないでやっちゃっていいのかな？


N = read_a_int()
S = []
for _ in range(N):
    S.append(read()[:-1])

cnt = Counter()
dame = 0
for s in S:
    cnt.update(s)
    dame += s.startswith(')') and s.endswith('(')

if cnt['('] != cnt[')']:
    print('No')
    exit()

if N - dame < 2:
    print('No')
    exit()

print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
M = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        M.append((right, left, left - right))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
M.sort()
nokori = []
for mr, ml, delta in M:
    if delta <= 0:
        nokori.append((mr, ml))
        continue
    L -= mr
    if L < 0:
        flag = 1
    L += ml
for mr, ml in nokori:
    L -= mr
    if L < 0:
        flag = 1
    L += ml

if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for i in range(N)]

C = [[0,0] for i in range(N)]

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



C.sort(key=lambda x : (x[1]+x[0]), reverse=True)
#print(C)
now = 0
ans = 'Yes'
for i in range(N):
    if now + C[i][1] < 0:
        ans = 'No'
        break
    now += C[i][0]
if sum(C[i][0] for i in range(N)) != 0:
    ans = 'No'

print(ans)

Submission status: Wrong Answer

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

nums=[0]*N
soko=[0]*N
for i in range(N):
  s=S[i]
  x=len(s)
  c=0
  for j in range(x):
    if s[j]=='(':
      c+=1
    else:
      c-=1
    if c<soko[i]:
      soko[i]=c
  
  nums[i]=c
  
res=[[nums[i], soko[i]] for i in range(N)]
res=sorted(res, key=itemgetter(1), reverse=True)

if sum(nums)!=0:
  print('No')
  exit()
  
h=0
for i in range(N):
  if h+res[i][1]<0:
    print('No')
    exit()
  h+=res[i][0]
  if h<0:
    print('No')
    exit()
print('Yes')

Submission status: Wrong Answer

Solution code:
print('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
for i in range(N):
    if A[i][0] <= 0:
        used[i] = True
        s += A[i][1]

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

B.sort(key=lambda x:(-x[1],x[0]))

for i in range(N):
    if used[i]:
        continue
    if s < A[i][0]:
        print('No')
        exit()
    else:
        s += A[i][1]
    
print('Yes')

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

print('Yes')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

tmp = []
for i,s in enumerate(S):
    tmp.append([s.count("(")-s.count(")"),i])

tmp.sort(reverse=True)
##print(tmp)
a = 0
b = 0
s = ""
for _,i in tmp:
    s += S[i]
##print(s)
for i in range(len(s)):
    if s[i] == "(":
        a += 1
    else:
        b += 1
    if b > a:
        print("No")
        exit()

if a-b == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
s = [input() for i in range(n)]
ruiseki = [[] for i in range(n)]

for i in range(n):
    ruiseki[i].append(0)
    for char in s[i]:
        if char == "(":
            ruiseki[i].append(ruiseki[i][-1] + 1)
        else:
            ruiseki[i].append(ruiseki[i][-1] - 1)

min_ = [0] * n
sum_ = [0] * n

for i in range(n):
    min_[i] = min(ruiseki[i])
    sum_[i] = ruiseki[i][-1]

info = [(sum_[i] + min_[i], min_[i], sum_[i]) for i in range(n)]
info = sorted(info, reverse=True)

now_m = 0
now_s = 0

for _, mi, su in info:
    if now_s + mi < 0:
        print("No")
        exit()
    now_s += su

if now_s == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = [input() for _ in range(N)]
    L = []
    for i in range(N):
        t = 0
        mint = 0
        for s in S[i]:
            if s == "(":
                t += 1
            else:
                t -= 1
            mint = min(mint, t)
        L.append((t, mint))
    L.sort(key=lambda x: x[0], reverse=True)
    L.sort(key=lambda x: x[1], reverse=True)
    t = 0
    for l, m in L:
        if t + m < 0:
            return False
        t += l
    if t == 0:
        return True
    return True


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

Submission status: Wrong Answer

Solution code:
n = int(input())

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

    neg = 0
    pos = 0
    for v in s:
        if v == '(':
            pos += 1
        else:
            if pos > 0:
                pos -= 1
            else:
                neg += 1
    stats.append((neg, pos))

stats.sort()

cur = 0
for i in range(n):
    neg, pos = stats[i]
    if cur < neg:
        print('No')
        exit()

    cur = cur - neg + pos

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[str]) -> bool:
    counts = defaultdict(int)
    total_closing = 0
    total_opening = 0
    for v in values:
        opening = 0
        closing = 0
        for c in v:
            if c == ")":
                if opening == 0:
                    closing += 1
                else:
                    opening -= 1
            if c == "(":
                opening += 1
        if closing + opening != 0:
            if (opening, closing) in counts:
                counts[(opening, closing)] -= 1
                if counts[(opening, closing)] == 0:
                    counts.pop((opening, closing))
            else:
                counts[(closing, opening)] += 1
        total_opening += opening
        total_closing += closing
    LOG.debug((counts))
    LOG.debug((total_opening, total_closing))
    if not counts:
        return True
    for closing, opening in counts:
        if closing == total_closing - opening and opening == total_opening - closing:
            return True
    # for (opening, closing), nb in counts.items():
    return False


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = []
    for _ in range(N):
        values.append(input().strip())
    result = solve(values)
    print("Yes" if result else "No")


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Wrong Answer

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

    tmp = 0
    lst1 = [] #合計としては伸びるけど途中にマイナスがあるもの
    lst1_append = lst1.append

    lst2 = [] #合計してもマイナス　途中もマイナス
    lst2_append = lst2.append

    for _ in range(N):
        S = list(input())
        min_ = 0
        total = 0
        for s in S:
            if s == '(':
                total += 1
            else:
                total -= 1
                min_ = min(min_, total)
        if min_ == 0:
            tmp += total
        else:
            if total > 0:
                lst1_append([min_, total])
            else:
                lst2_append([min_, total])

    lst1.sort(key = lambda x: x[0], reverse = True) #途中での小さくなり方が小さいものから入れる どんどん条件は緩くなるから小さくなる値が0に近いものから
    for a, b in lst1:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b
    lst2.sort(key = lambda x: x[0], reverse = False) #どんどん条件が厳しくなるから、より小さいもの　= 0から遠いもの　から使っていく
    lst2.sort(key = lambda x: x[1], reverse = True)

    # print (lst2)
    for a, b in lst2:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
LR = [[0]*2 for i in range(N)]
for i in range(N):
    S = input()
    M = len(S)
    L = 0
    R = 0
    R0 = 0
    t = 0
    if S[0]==")":
        while t<M:
            if S[t]==")":
                R0+=1
                t+=1
            else:
                t+=1
                break
    while t<M:
        if S[t]=="(":
            t+=1
            L+=1
        else:
            t+=1
            R+=1
    if L>R:
        LR[i][0]=L-R
        LR[i][1]=R0
    if L<R:
        LR[i][0]=0
        LR[i][1]=R0+R-L
    if L==R:
        LR[i][0]=0
        LR[i][1]=R0

LP = 0
RP = 0
minLS = float('inf')
minRS = float('inf')
LS = 0
RS = 0
for i in range(N):
    L = LR[i][0]
    R = LR[i][1]
    if (L==0)and(R==0):
        continue
    elif L==0:
        RP += R
    elif R==0:
        LP += L
    else:
        LS += L
        RS += R
        if LS < minLS:
            minLS = LS
        if RS < minRS:
            minRS = RS

if (LP==RP)and(LS==0)and(RS==0):
    print("Yes")

else:
    if LS>RS:
        RS = minRS
        LS = LS-RS+minRS
    elif LS>RS:
        RS = RS-LS+minLS
        LS = minLS
    elif LS==RS:
        RS = min(minLS,minRS)
        LS = min(minLS,minRS)
    if (LS<=RP)and(RS<=LP):
        print("Yes")
    else:
        print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
R = L = 0
for _ in range(n):
    s = input()
    p = 0
    for i in range(len(s)):
        c = s[i]
        if p <= 0 and c == ")":
            L += 1
        if c == "(":
            p += 1
        if p > 0  and c==")":
            p -= 1
    R += p
if R == L:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
M = []
for _ in range(n):
    s = input()
    right = 0
    left = 0
    for w in s:
        if w == "(":
            left += 1
        if w == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    if left > 0 and right > 0:
        M.append((right, left, left - right))
    elif left == 0 and right > 0:
        R += right
    elif left > 0 and right == 0:
        L += left
M.sort()
nokori = []
for mr, ml, delta in M:
    if delta < 0:
        nokori.append((mr, ml))
    L -= mr
    if L < 0:
        flag = 1
    L += ml
for mr, ml in nokori:
    L -= mr
    if L < 0:
        flag = 1
    L += ml

if L != R:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
def do(s):
    l, r = 0, 0
    for i in range(len(s)):
        if s[i] == "(":
            r += 1
        elif s[i] == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
    #print(s, l, r)
    return (l,r)

n = int(input())
dat = []

curl, curr = 0, 0
for i in range(n):
    s = input()
    l ,r = do(s)
    if l != 0 or r != 0:
        if l == 0:
            curr += r
        else:
            curl += l
        dat.append( [l,r] )
        continue

curl, curr = curl - min(curr, curl), curr - min(curr, curl)
#print(curr, curl)

for i in range(len(dat)):
    newl , newr = dat[i]
    caneraseL = min(curl, newr)
    caneraseR = min(curr, newl)
    if caneraseL == caneraseR:
        if curl > curr: # Lを消したい = newは左につける
            # 左につける ver00
            if curl >  newr: # いまのLの方が多いなら
                curl, curr = newl + (curl - newr), curr
            else:
                curl, curr = newl, curr + (newr - curl)
        else: # Rを消す = newは右につける
            # 右につける ver00
            if curr >  newl: # いまのRの方が多いなら
                curl, curr = curl, newr + (curr - newl)
            else:
                curl, curr = curl + (newl - curr), newr
    elif caneraseR > caneraseL:
        # 右につける ver00
        if curr > newl:  # いまのRの方が多いなら
            curl, curr = curl, newr + (curr - newl)
        else:
            curl, curr = curl + (newl - curr), newr
    else: # caneraseR < caneraseL
        # 左につける ver00
        if curl > newr:  # いまのLの方が多いなら
            curl, curr = newl + (curl - newr), curr
        else:
            curl, curr = newl, curr + (newr - curl)
#print(curl,curr)
print("Yes" if curl == curr == 0 else "No")

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
s=[input() for i in range(n)]
lst=[[0]*2 for i in range(n)]

for i in range(n):
    l,r=0,0
    for j in range(len(s[i])):
        if s[i][j]==")":
            if r==0:
                l+=1
            else:
                r-=1
        if s[i][j]=="(":
            r+=1
    lst[i][0]=l
    lst[i][1]=r
# print(lst)
lst.sort(key=lambda x: (x[0],-x[1]))
# print(lst)
lastn=-1
for i in range(n):
    if lst[-1-i][1]==0:
        lastn=n-1-i
if lastn==-1:
    print("No")
    quit()
tmp=0
for i in range(n):
    if i==lastn:
        continue
    tmp-=lst[i][0]
    if tmp<0:
        print("No")
        break
    tmp+=lst[i][1]
else:
    tmp-=lst[lastn][0]
    if tmp<0:
        print("No")
    
    if tmp==0:
        print("Yes")
    else:
        print("No")