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 heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) #プログラムを終了

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] #入力の右端の値を除去
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': #前から探索
            cnt += 1
            # print('+cnt:{}'.format(cnt))
            M = max(M,cnt) #'('が多い場合はcnt=0,')'が多い場合はcntは'('と')'の個数の差
            # print('M:{}'.format(M))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: #後ろから探索
        if t == ')':
            cnt += 1
            # print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
            m = min(m,cnt) #')'が多い場合はcnt=0,'('が多い場合はcntは'('と')'の個数の差
            # print('m:{}'.format(m))
    if cnt > 0:
        minus.append((-m,cnt))
    elif cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) #プログラムを終了

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] #入力の右端の値を除去
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': #前から探索
            cnt += 1
            # print('+cnt:{}'.format(cnt))
            M = max(M,cnt) #'('が多い場合はcnt=0,')'が多い場合はcntは'('と')'の個数の差
            # print('M:{}'.format(M))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: #後ろから探索
        if t == ')':
            cnt += 1
            # print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            # print('-cnt:{}'.format(cnt))
            m = min(m,cnt) #')'が多い場合はcnt=0,'('が多い場合はcntは'('と')'の個数の差
            # print('m:{}'.format(m))
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Wrong Answer

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

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, rev_r)
        min_revl = min(min_revl, rev_l)

if min_revr == 10**20:
    min_revr = 0
if min_revl == 10**20:
    min_revl = 0

if left+rev_l == rev_r+right and left >= 1 and 1 <= right:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, rev_r)
        min_revl = min(min_revl, rev_l)

if min_revr == 10**20:
    min_revr = 0
if min_revl == 10**20:
    min_revl = 0

if left+rev_l == rev_r+right and left > min_revr and min_revl < right:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) #プログラムを終了

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] #入力の右端の値を除去
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': #前から探索
            cnt += 1
            M = max(M,cnt) #'('が多い場合はcnt=0,')'が多い場合はcntは'('と')'の個数の差
        else:
            cnt -= 1
    cnt = 0
    for t in s[::-1]: #後ろから探索
        if t == ')':
            cnt += 1
        else:
            cnt -= 1
            m = min(m,cnt) #')'が多い場合はcnt=0,'('が多い場合はcntは'('と')'の個数の差
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def end(flag):
    if flag:
        print('Yes')
    else:
        print('No')
    exit(0) #プログラムを終了

n = int(input())
plus = []
minus = []
zero = []
total = 0
for i in range(n):
    s = input()[:-1] #入力の右端の値を除去
    cnt = 0
    M = 0
    m = 0
    for t in s:
        if t == ')': #前から探索
            cnt += 1
            print('+cnt:{}'.format(cnt))
            M = max(M,cnt) #'('が多い場合はcnt=0,')'が多い場合はcntは'('と')'の個数の差
            print('M:{}'.format(M))
        else:
            cnt -= 1
            print('-cnt:{}'.format(cnt))
    cnt = 0
    for t in s[::-1]: #後ろから探索
        if t == ')':
            cnt += 1
            print('+cnt:{}'.format(cnt))
        else:
            cnt -= 1
            print('-cnt:{}'.format(cnt))
            m = min(m,cnt) #')'が多い場合はcnt=0,'('が多い場合はcntは'('と')'の個数の差
            print('m:{}'.format(m))
    # if cnt > 0:
    #     minus.append((-m,cnt))
    if cnt == 0:
        zero.append((-m,M))
    else:
        plus.append((M,-cnt))
    S = (M,-cnt)
    total += cnt
if total != 0:
    end(0)
plus.sort()
minus.sort()
cnt = 0
for need,increase in plus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
cnt = 0
for need,increase in minus:
    if cnt < need:
        end(0)
    else:
        cnt += increase
for m,M in zero:
    if m > cnt or M > cnt:
        end(0)
end(1)

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    left, right = [], []
    for c in s:
        if 2*c.count('(') - len(c) > 0:
            left.append(c)
        else:
            right.append(c)

    left.sort(key = lambda x: x.count('('))
    right.sort(key = lambda x: x.count(')'), reverse = True)
    left.extend(right)
    sum = 0
    for v in left:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    left, right = [], []
    for c in s:
        if 2*c.count('(') - len(c) > 0:
            left.append(c)
        else:
            right.append(c)

    left.sort()
    right.sort(reverse = True)
    left.extend(right)
    sum = 0
    for v in left:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print("No" if m else "Yes")

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())

def canArrangeBranket(brankets):
    totup = 0
    uplist = []
    for branket in brankets:
        up = 0
        minup = 0
        for c in list(branket):
            if c == '(':
                up += 1
            else:
                up -= 1
                minup = min(minup , up)
        totup += up
        uplist.append((minup , up))
    if totup != 0:
        return False
    pos_brankets = list(filter(lambda x : x[1] >= 0 , uplist))
    neg_brankets = list(filter(lambda x : x[1] < 0 , uplist))
    pos_brankets.sort(key=itemgetter(0), reverse=True)
    neg_brankets.sort(key=itemgetter(0))
    neg_brankets.sort(key=itemgetter(1), reverse=True)
    curup = 0
    for (minup , up) in pos_brankets + neg_brankets:
        if minup + curup < 0:
            return False
        curup += up
    return True

branketList = []
for i in range(N):
    l = input()
    branketList.append(l)

if canArrangeBranket(branketList):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    left, right = [], []
    for c in s:
        if 2*c.count('(') - len(c) > 0:
            left.append(c)
        else:
            right.append(c)

    left.sort()
    right.sort()
    left.extend(right)
    sum = 0
    for v in left:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())

def canArrangeBranket(brankets):
    totup = 0
    uplist = []
    for branket in brankets:
        up = 0
        minup = 0
        for c in list(branket):
            if c == '(':
                up += 1
            else:
                up -= 1
                minup = min(minup , up)
        totup += up
        uplist.append((minup , up))
    if totup != 0:
        return False
    pos_brankets = list(filter(lambda x : x[1] >= 0 , uplist))
    neg_brankets = filter(lambda x : x[1] < 0 , uplist)
    pos_brankets.sort(key=itemgetter(0), reverse=True)
    curup = 0
    for (minup , up) in pos_brankets:
        if minup + curup < 0:
            return False
        curup += up
    return True

branketList = []
for i in range(N):
    l = input()
    branketList.append(l)

if canArrangeBranket(branketList):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    left, right = [], []
    for c in s:
        if c[0] == '(':
            left.append(c)
        else:
            right.append(c)

    left.sort()
    right.sort()
    left.extend(right)
    sum = 0
    for v in left:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print('YNeos'[not m::2])

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    left, right = [], []
    for c in s:
        if c[0] == '(':
            left.append(c)
        else:
            right.append(c)

    left.sort()
    right.sort(reverse=True)
    left.extend(right)
    sum = 0
    for v in left:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
    if m+c<0:print("No");break
    m+=d
else:print('NYoe s'[m::2])

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*s=open(0).read().split()
u=[[min(accumulate(t,lambda a,b: a+(1 if b=="(" else -1),initial=0)),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if m+c<0:print("No");break;m+=d
else:
    print("No" if m else "Yes")

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N = int(input())

def canArrangeBranket(brankets):
    totup = 0
    uplist = []
    for branket in brankets:
        up = 0
        minup = 0
        for c in list(branket):
            if c == '(':
                up += 1
            else:
                up -= 1
                minup = min(minup , up)
        totup += up
        uplist.append((minup , up))
    if totup != 0:
        return False
    uplist.sort(key=itemgetter(1), reverse=True)
    uplist.sort(key=itemgetter(0), reverse=True)
    curup = 0
    for (minup , up) in uplist:
#        print(minup , up , curup)
        if minup + curup < 0:
            return False
        curup += up
    return True

branketList = []
for i in range(N):
    l = input()
    branketList.append(l)

if canArrangeBranket(branketList):
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]
now=0
for c in chain(sorted([x for x in st if x[1]>=0])[::-1],sorted([x for x in st if x[1]<0],key=lambda z:z[1]-z[0])[::-1]):
    if now+c[0]<0:
        print("No");exit()
    now+=c[1]
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
flag = 0
ML = []
MM = []
MR = []
L = 0
R = 0
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
        saisho = min(saisho, cur)
    if saisho == 0:
        if cur > 0:
            L += cur
        elif cur < 0:
            R += -cur
    else:
        if cur > 0:
            ML.append((saisho, cur))
        elif cur < 0:
            MR.append((saisho, cur))
        else:
            MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort()
now = L
for saisho, delta in ML:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MM:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MR:
    if now + saisho < 0:
        flag = 1
    now += delta

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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

N=input_one_number()

S=[]
Sparam = []
for i in range(N):
    si = input()
    S.append(si)

    bottom = 0
    frontend = 0
    for j in range(len(si)):
        if si[j]=='(':
            frontend += 1
        else:
            frontend -= 1
        bottom = min(bottom,frontend)

    Sparam.append([frontend,bottom])


summ = 0
for i in range(N):
    summ += Sparam[i][0]
if summ != 0:
    print("No")
    exit()


now = 0
#pattern 1 2 3
ii = 0
while ii < len(Sparam):
    if Sparam[ii][1] == 0:
        now += Sparam[ii][0]
        Sparam.pop(ii)
        ii-=1
    ii += 1

#pattern 8 
ii = 0
while ii < len(Sparam):
    if Sparam[ii][0] > 0 and Sparam[ii][1] + now >= 0:
        now += Sparam[ii][0]
        Sparam.pop(ii)
        ii -= 1
    ii+=1

#pattern 8 (retry)
ii = 0
while ii < len(Sparam):
    if Sparam[ii][0] > 0:
        if Sparam[ii][1] + now < 0:
            print('No')
            exit()

        now += Sparam[ii][0]
        Sparam.pop(ii)
        ii -= 1
    ii+=1

#pattern 6
ii = 0
while ii < len(Sparam):
    if Sparam[ii][0] == 0:
        if Sparam[ii][1] + now < 0:
            print('No')
            exit()

        now += Sparam[ii][0]
        Sparam.pop(ii)
        ii -= 1
    ii+=1


#pattern 7 
ii = 0
while ii < len(Sparam):
    if Sparam[ii][1] < Sparam[ii][0]:
        now += Sparam[ii][0]
        if now < 0:
            print('No')
            exit()
        Sparam.pop(ii)
        ii -= 1
    ii+=1


# pattern 4 5
for i in range(len(Sparam)):
    now += Sparam[i][0]

if now<0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*i.count("(")-len(i) for i in s]
if sum(t)!=0:
    print("No");exit()
#pypyではinitialだめ
st=[[min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0)),t_] for s_,t_ in zip(s,t)]

now=0
v=list(filter(lambda x:x[0]>=0,st))
w=list(filter(lambda x:x[0]<0,st))
v.sort()
w.sort()

for c in chain(v[::-1],w[::-1]):
    if now+c[1]<0:
        print("No");exit()
    now+=c[0]
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
flag = 0
ML = []
MM = []
MR = []
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
        saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((saisho, cur))
    else:
        MM.append((saisho, cur))
ML.sort(key=lambda X: [-X[0], -X[1]])
MR.sort(key=lambda X: [X[0], -X[1]])
now = 0
for saisho, delta in ML:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MM:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MR:
    if now + saisho < 0:
        flag = 1
    now += delta

if now != 0:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
flag = 0
ML = []
MM = []
MR = []
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
        saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((saisho, cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort()
now = 0
for saisho, delta in ML:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MM:
    if now + saisho < 0:
        flag = 1
    now += delta
for saisho, delta in MR:
    if now + saisho < 0:
        flag = 1
    now += delta

if now != 0:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    lr.append([l,r])
idlemax=10**9
lr.sort(key=lambda x:x[1]*(idlemax)-x[0])
L=0
R=0
#print(lr)
for l,r in lr:

    L-=r
    if L<0:
        print("No")
        exit()
    L+=l

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

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    lr.append([l,r])
idlemax=10**9
lr.sort(key=lambda x:x[1]*(idlemax)-x[0])
L=0
R=0
print(lr)
for l,r in lr:

    L-=r
    if L<0:
        print("No")
        exit()
    L+=l

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

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Wrong Answer

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

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    print(l)
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
S=[input() for i in range(N)]
lr=[]
for n in range(N):
    l=0
    r=0
    for i in range(len(S[n])):
        if S[n][i]=="(":
            l+=1
        else:
            if l>0:
                l-=1
            else:
                r+=1
    #print(l,r)
    lr.append([l,r])
idlemax=10**9
lr.sort(key=lambda x:x[1]*(idlemax)-x[0])
L=0
R=0
#print(lr)
for l,r in lr:

    L-=r
    if L<0:
        print("No")
        exit()
    L+=l

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

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n=int(input())
s=[input() for i in range(n)]
t=map(lambda x:2*x.count("(")-len(x),s)
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Wrong Answer

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

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=map(lambda x:2*x.count("(")-len(x),s)
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
flag = 0
ML = []
MM = []
MR = []
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        else:
            cur -= 1
        saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((saisho, cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort()
now = 0
for saisho, delta in ML:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho
for saisho, delta in MM:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho
for saisho, delta in MR:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho

if now != 0:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
from sys import exit
from itertools import accumulate,chain
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
#pypyではinitialだめ
st=[[t[i],min(accumulate(s[i],lambda a,b: a+(1 if b=="(" else -1),initial=0))] for i in range(n)]

now2=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now2+sub[1]<0:
        print("No");exit()
    now2+=sub[0]
print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
R = 0
L = 0
flag = 0
ML = []
MM = []
MR = []
for _ in range(n):
    s = input()
    saisho = 0
    cur = 0
    for w in s:
        if w == "(":
            cur += 1
        if w == ")":
            cur -= 1
        saisho = min(saisho, cur)
    if cur > 0:
        ML.append((saisho, cur))
    elif cur < 0:
        MR.append((saisho, cur))
    else:
        MM.append((saisho, cur))
ML.sort(reverse=True)
MR.sort()
now = 0
for saisho, delta in ML:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho
for saisho, delta in MM:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho
for saisho, delta in MR:
    now += saisho
    if now < 0:
        flag = 1
    now += delta - saisho

if now != 0:
    flag = 1
if flag:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_left = []
lst_right = []
for i in range(n):
  s = input()
  h = 0
  b = 0
  for e in s:
    if e == "(":
      h += 1
    else:
      h -= 1
      b = min(b, h)
  if h>=0:
    lst_left.append((b, h))
  else:
    lst_right.append((b, h))
#lst_left = sorted(lst_left, key=lambda x:x[1], reverse=True)
lst_left = sorted(lst_left, key=lambda x:x[0], reverse=True)
#lst_right = sorted(lst_right, key=lambda x:x[0], reverse=True)
lst_right = sorted(lst_right, key=lambda x:x[1], reverse=True)
h = 0

for i in range(len(lst_left)):
  if h + lst_left[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_left[i][1]
for i in range(len(lst_right)):
  if h + lst_right[i][0] < 0:
    print("No")
    exit()
  else:
    h += lst_right[i][1]
if h == 0:
  print("Yes")
else:
  print("No")