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:
def main():
    import sys
    from collections import deque
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    p, m = 0, 0
    p_, m_ = 0, 0
    pq = deque([])
    mq = deque([])
    for n in range(N):
        s = input().strip()
        mini = 0
        dst = 0
        for ss in [1 if ss == '(' else -1 for ss in s]:
            dst += ss
            mini = min(dst, mini)
        
        if dst >= 0:
            pq.append((mini, dst))
        elif dst < 0:
            mq.append((mini, dst))
    pq = sorted(pq, reverse=True)
    mq = sorted(mq)
    p = 0
    for mini, dst in pq + mq:
        if - mini > p:
            print('No')
            exit()
        p += dst
    if p != 0:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
a = []
NINF = -10**10
for i in s:
    mi = 0
    tmp = 0
    for c in i:
        if c=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp<mi:
            mi = tmp
    a.append((mi if mi<0 else NINF, tmp))
a.sort(key=lambda x:(x[0],-x[1]))
tmp = 0
for i, j in a:
    if i>NINF and tmp+i<0:
        print('No')
        break
    tmp += j
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
def check():
    N = int(input())
    lr = [[0,0] for _ in range(N)] #[l,r]
    for i in range(N):
        S = list(input())
        for s in S:
            if s==')': #lの処理
                if lr[i][1]<0:
                    lr[i][1]+=1 #rが受け止めてくれる
                else:
                    lr[i][0]+=1 #rが受け止めてくれない
            else: #rの処理
                lr[i][1] -= 1 #ただ増えるだけ
    lr.sort(key=lambda x: (x[0], -x[0]+x[1]))
    now = 0
    for l,r in lr:
        if now <l:
            return 'No'
        now -= l+r
    if now==0:
        return 'Yes'
    return 'No'
print(check())

Submission status: Wrong Answer

Solution code:
def check():
    N = int(input())
    lr = [[0,0] for _ in range(N)] #[l,r]
    for i in range(N):
        S = list(input())
        for s in S:
            if s==')': #lの処理
                if lr[i][1]<0:
                    lr[i][1]+=1 #rが受け止めてくれる
                else:
                    lr[i][0]+=1 #rが受け止めてくれない
            else: #rの処理
                lr[i][1] -= 1 #ただ増えるだけ
    lr.sort(key=lambda x: (x[0], x[0]-x[1]))
    now = 0
    for l,r in lr:
        if now <l:
            return 'No'
        now -= l+r
    if now==0:
        return 'Yes'
    return 'No'
print(check())

Submission status: Wrong Answer

Solution code:
import numpy  as np


def parse(brackets):
    m = 0
    f = 0
    for c in brackets:
        if c == "(":
            f += 1
        else:
            f -= 1
        if m > f:
            m = f
    return m, f


def climbable(g, reverse=False):
    if reverse:
        g = g * np.array([1,-1])
        g[:,0] = np.sum(g)
    top = np.sum(g[g[:,0]>=0][:,1])
    v = g[g[:,0]<0]
    while len(v) > 0:
        flag = v[:,0]+top>=0
        if not np.any(flag):
            return False
        if np.all(flag):
            return True
        top += np.sum(v[flag][:,1])
        v = v[np.logical_not(flag)]
    return True


def main():
    n = int(input())
    g = np.stack([np.array(parse(input().strip()), dtype=int) for _ in range(n)])
    if np.sum(g, axis=0)[1] != 0:
        return False
    f = g[:, 1]
    return climbable(g[f>=0]) and climbable(g[f<0], reverse=True)


if __name__ == "__main__":
    print("Yes" if main() else "No")

Submission status: Wrong Answer

Solution code:
# F - Bracket Sequencing

from itertools import chain

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

def parse(s):
    "バランスしていない閉じ括弧数, 開き括弧数"
    cl, op = 0, 0
    for c in s:
        if c == '(':
            op += 1
        elif op > 0:
            op -= 1
        else:
            cl += 1
    return (cl, op)

inc = []  # 開き括弧が多い
dec = []  # 閉じ括弧が多い
for s in ss:
    cl, op = parse(s)
    if cl < op:
        inc.append((cl, op))
    else:
        dec.append((cl, op))
peak = 0
inc.sort()
dec.sort(reverse=True)
for cl, op in chain(inc, dec):
    if peak < cl:
        print('No')
        exit()
    peak += op - cl
print('Yes' if peak == 0 else 'No')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            else: mm.append((w,e))
        else: p += e

    mp.sort(reverse=True)
    for w,e in mp:
        if p + w < 0:
            print('No')
            exit(0)
        p += e
    min_p = p
    mm.sort(reverse=True)
    if mm:
        min_p += mm[0][0]
        p += mm[0][1]
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

    for w,e in mm[1:]:
        min_p = min(min_p,max(min_p + e, p + w))
        p += e
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            else: mm.append((w,e))
        else: p += e

    mp.sort(reverse=True)
    for w,e in mp:
        if p + w < 0:
            print('No')
            exit(0)
        p += e
    min_p = p
    mm.sort(reverse=True)
    if mm:
        min_p += mm[0][0]
        p += e
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

    for w,e in mm[1:]:
        min_p = min(min_p,max(min_p + e, p + w))
        p += e
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            else: mm.append((w,e))
        else: p += e

    mp.sort(reverse=True)
    for w,e in mp:
        if p + w < 0:
            print('No')
            exit(0)
        p += e
    min_p = p
    mm.sort(reverse=True)
    if mm:
        min_p += mm[0][0]
    for w,e in mm:
        min_p = min(min_p,max(min_p + e, p + w))
        p += e
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            else: mm.append((w,e))
        else: p += e

    mp.sort(reverse=True)
    for w,e in mp:
        if p + w < 0:
            print('No')
            exit(0)
        p += e
    min_p = p
    mm.sort(reverse=True)
    for w,e in mm:
        min_p = min(min_p,max(min_p + e, p + w))
        p += e
        if p < 0 or min_p < 0:
            print('No')
            exit(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

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


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

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

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

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

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


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

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
n = int(input())
scop = [[0,0] for i in range(n)] #高低差,min値
scom = [[0,0] for i in range(n)]
pi = 0
mi = 0
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop[pi] = [ms,sa]
        pi += 1
    elif not sa == ms:
        scom[mi] = [ms,sa]
        mi += 1
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
    if pi < 0:
        break
    pi -= 1
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
    if mi < 0:
        break
    mi -= 1

print("Yes")

Submission status: Wrong Answer

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

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

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

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

    ways = sorted(ways, key=lambda x:x[0], reverse=True)
    while ways:
        for idx, (go, max_depth) in enumerate(ways):
            if current + max_depth >= 0:
                current += go
                del ways[idx]
                continue
        print('No')
        return None
    if current == 0:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
n = int(input())
scop = [] #高低差,min値
scom = []
scomn = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif sa == ms:
        scomn.append([ms,sa])
    else:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

'''
scop.sort(reverse = True)
scom.sort()
'''

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    else:
        now += i[1]

print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
a = []
for i in s:
    mi = 0
    tmp = 0
    for c in i:
        if c=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp<mi:
            mi = tmp
    a.append((mi, tmp))
a.sort(key=lambda x:(-x[0],-x[1]))
tmp = 0
for i, j in a:
    if tmp+i<0:
        print('No')
        break
    tmp += j
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

        if count > N:
            print('No')
            return None
    if current == 0:
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = []
for _ in range(n):
    s.append(input())
a = []
for i in s:
    mi = 0
    tmp = 0
    for c in i:
        if c=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp<mi:
            mi = tmp
    a.append((mi, tmp))
a.sort(key=lambda x:-x[0])
tmp = 0
for i, j in a:
    if tmp+i<0:
        print('No')
        break
    tmp += j
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

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

        if count > N:
            print('No')
            break
    if current == 0:
        print('Yes')
    else:
        print('No')
if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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

pos = []
neg = []
for s in S:
    sm = 0
    mn = 0
    for c in s:
        if c=='(':
            sm += 1
        else:
            sm -= 1
            mn = min(mn, sm)
    if sm >= 0:
        pos.append((mn,sm))
    else:
        neg.append((mn-sm, -sm))

pos.sort()
neg.sort()

hp = 0
for m,s in pos:
    if hp + m < 0:
        print('No')
        exit()
    hp += s

hn = 0
for m,s in neg:
    if hn + m < 0:
        print('No')
        exit()
    hn += s

print('Yes' if hp==hn else 'No')

Submission status: Wrong Answer

Solution code:
N = int(input())

def cnt(s):
    r = [0] * (len(s)+1)
    for i, v in enumerate(s):
        if v == '(':
            r[i+1] = r[i] + 1
        else:
            r[i+1] = r[i] - 1
    return r[0], r[-1], min(r)

# S1 := 始点 < 終点
S1 = []
# S2 := 始点 => 終点
S2 = []
for i in range(N):
    s = input()
    t = tuple(cnt(s))
    if t[1] > 0:
        S1.append(t)
    else:
        S2.append(t)
def main():
    # Sの終点を合計して0じゃなかったら、終わり
    if sum([s[1] for s in S1]) + sum([s[1] for s in S2]) != 0:
        print("No")
        return
    # S1の中で、最小値が大きい順に並べる
    X1 = sorted(S1, key=lambda x: x[2], reverse=True)
    # S2の中で、最小値が小さい順に並べる
    X2 = sorted(S2, key=lambda x: (-x[2], x[1]))
    T = 0
    # X1を並べきった後に、X2を並べて実現可能か調べる、終点を合計して0になることは確認済み
    for s, t, mi in X1:
        if T + mi < 0:
            print("No")
            return
        T += t
    for s, t, mi in X2:
        if T + mi < 0:
            print("No")
            return
        T += t
    print("Yes")

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

def cnt(s):
    r = [0] * (len(s)+1)
    for i, v in enumerate(s):
        if v == '(':
            r[i+1] = r[i] + 1
        else:
            r[i+1] = r[i] - 1
    return r[0], r[-1], min(r)

# S1 := 始点 < 終点
S1 = []
# S2 := 始点 => 終点
S2 = []
for i in range(N):
    s = input()
    t = tuple(cnt(s))
    if t[1] > 0:
        S1.append(t)
    else:
        S2.append(t)
def main():
    # Sの終点を合計して0じゃなかったら、終わり
    if sum([s[1] for s in S1]) + sum([s[1] for s in S2]) != 0:
        print("No")
        return
    # S1の中で、最小値が大きい順に並べる
    X1 = sorted(S1, key=lambda x: x[2], reverse=True)
    # S2の中で、最小値が小さい順に並べる
    X2 = sorted(S2, key=lambda x: x[2])
    T = 0
    # X1を並べきった後に、X2を並べて実現可能か調べる、終点を合計して0になることは確認済み
    for s, t, mi in X1:
        if T + mi < 0:
            print("No")
            return
        T += t
    for s, t, mi in X2:
        if T + mi < 0:
            print("No")
            return
        T += t
    print("Yes")

main()

Submission status: Wrong Answer

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

s.sort(key=lambda x: (len(x)-2*(x.count('(')), x))
tmp = 0
for i in s:
    for c in i:
        if c=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < 0:
            print('No')
            break
    else:
        continue
    break
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((w,e))
            else: mm.append((w,e))
        else: p += e

    mp.sort(reverse=True)
    mm.sort()
    for w,e in mp + mm:
        if p < -w:
            print('No')
            exit(0)
        p += e
    if p == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    S = []
    for i in range(N):
        _ = input()
        S.append([ _.count('(') - _.count(')'), _ ])

    if sum([S[_][0] for _ in range(N)]) != 0:
        print('No')
        return

    S.sort(reverse=True)

    cnt = 0
    for s in S:
        for c in s[1]:
            cnt += c.count('(') - c.count(')')
            if cnt < 0:
                print('No')
                return
    print('Yes')


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

s.sort()
tmp = 0
for i in s:
    for c in i:
        if c=='(':
            tmp += 1
        else:
            tmp -= 1
        if tmp < 0:
            print('No')
            break
    else:
        continue
    break
else:
    if tmp==0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    p = 0
    mp = []
    mm = []
    for _ in range(N):
        w = INF
        e = 0
        for s in sys.stdin.readline().rstrip():
            if s == '(': e += 1
            else: e -= 1
            w = min(w,e)
        if w < 0:
            if e > 0 :mp.append((e,w))
            else: mm.append((e,w))
        else: p += e

    mp.sort(key=lambda x:-x[1])
    mm.sort(reverse=True)
    for e,w in mp + mm:
        if p < -w:
            print('No')
            exit(0)
        p += e
    if p == 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    l_0 = []
    r_0 = []
    ls_plus = []
    ls_minus = []
    sum_l = 0
    sum_r = 0
    for i in range(n):
        s = input()
        left, right = 0, 0
        for j in range(len(s)):
            if s[j] == '(':
                right += 1
            else:
                if right > 0:
                    right -= 1
                else:
                    left += 1
        if left == right == 0:
            continue

        if left == 0:
            l_0.append((left, right))
        elif right == 0:
            r_0.append((left, right))
        elif left < right:
            ls_plus.append((left, right))
        else:
            ls_minus.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls_plus) == len(ls_minus) == len(l_0) == len(r_0) == 0:
        print("Yes")
        return

    if len(l_0) == 0 or len(r_0) == 0:
        print("No")
        return
    if sum_l != sum_r:
        print("No")
        return

    # r-lの大きい順
    ls_plus.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls_plus.sort(key=lambda x: x[0])

    # l-rの小さい順
    ls_minus.sort(key=lambda x: x[0] - x[1])
    # lの大さい順
    ls_minus.sort(key=lambda x: x[0], reverse=True)

    now_r = 0
    for ll in l_0:
        now_r += ll[1]

    # now_l = 0
    for i in range(1, len(ls_plus)):
        # l = ls[i][0]
        r = ls_plus[i][1]
        x = now_r - ls_plus[i][0]
        if x >= 0:
            # now_l = now_l
            now_r = x + r
        else:
            print("No")
            return

    for i in range(1, len(ls_minus)):
        # l = ls[i][0]
        r = ls_minus[i][1]
        x = now_r - ls_minus[i][0]
        if x >= 0:
            # now_l = now_l
            now_r = x + r
        else:
            print("No")
            return

    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    l_0 = []
    r_0 = []
    ls_plus = []
    ls_minus = []
    sum_l = 0
    sum_r = 0
    for i in range(n):
        s = input()
        left, right = 0, 0
        for j in range(len(s)):
            if s[j] == '(':
                right += 1
            else:
                if right > 0:
                    right -= 1
                else:
                    left += 1
        if left == right == 0:
            continue

        if left == 0:
            l_0.append((left, right))
        elif right == 0:
            r_0.append((left, right))
        elif left < right:
            ls_plus.append((left, right))
        else:
            ls_minus.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls_plus) == len(ls_minus) == len(l_0) == len(r_0) == 0:
        print("Yes")
        return

    if len(l_0) == 0 or len(r_0) == 0:
        print("No")
        return
    if sum_l != sum_r:
        print("No")
        return

    # r-lの大きい順
    ls_plus.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls_plus.sort(key=lambda x: x[0])

    # l-rの大きい順
    ls_minus.sort(key=lambda x: x[0] - x[1], reverse=True)
    # lの大さい順
    ls_minus.sort(key=lambda x: x[0], reverse=True)

    now_r = 0
    for ll in l_0:
        now_r += ll[1]

    # now_l = 0
    for i in range(1, len(ls_plus)):
        # l = ls[i][0]
        r = ls_plus[i][1]
        x = now_r - ls_plus[i][0]
        if x >= 0:
            # now_l = now_l
            now_r = x + r
        else:
            print("No")
            return

    for i in range(1, len(ls_minus)):
        # l = ls[i][0]
        r = ls_minus[i][1]
        x = now_r - ls_minus[i][0]
        if x >= 0:
            # now_l = now_l
            now_r = x + r
        else:
            print("No")
            return
    
    print("Yes")


main()