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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# bracket sequencing


import sys


class newint(object):
    def __init__(self, mini, maxi):
        # オブジェクトの定義
        self.mini = mini
        self.maxi = maxi

    def __lt__(self, other):
        # 比較演算子
        K = min(self.mini, self.maxi-other.mini) - \
            min(other.mini, other.maxi-self.mini)
        if K >= 0:
            return True
        else:
            return False


def input(): return sys.stdin.readline().rstrip()


N = int(input())
data = []
for _ in range(N):
    plus = 0
    minus = 0
    sums = 0
    S = input()
    for i in range(len(S)):
        if S[i] == "(":
            sums += 1
            plus = max(plus, sums)
        else:
            sums -= 1
            minus = min(minus, sums)
    data.append(newint(minus, sums-minus))

data.sort()

flag = True
now_value = 0
for x in data:
    now_value += x.mini
    if now_value < 0:
        flag = False
        break
    now_value += x.maxi
if flag and now_value == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input() for i in range(n)]
l, r = [], []
for i in s:
    a, b = 0, 0
    for j in range(len(i)):
        if i[j] == "(":
            b += 1
        if i[j] == ")":
            if b <= 0:
                a -= 1
            else:
                b += 1
    if b - a > 0:
        l.append([a, b])
    else:
        r.append([a, b])
l.sort(key=lambda x:x[0])
r.sort(key=lambda x:x[1], reverse=True)
li = l + r
ans = 0
for i in li:
    ans -= i[0]
    if ans < 0:
        exit(print("No"))
    ans += i[1]
print("Yes" if ans == 0 else "No")

Submission status: Wrong Answer

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

n = int(input())

plus = []
minus = []
for _ in range(n):
    min_s = 0
    ts = 0
    s = input().strip()
    for c in s:
        ts += 1 if c == '(' else -1
        min_s = min(ts, min_s)
    if ts >= 0:
        plus.append((min_s, ts))
    else:
        minus.append((min_s - ts, -ts))
        # min_s = 0
        # ts = 0
        # for c in s[::-1]:
        #     ts += 1 if c == ')' else -1
        #     min_s = min(ts, min_s)
        # minus.append((min_s, ts))

plus.sort()
minus.sort()

s1 = 0
for m, t in plus:
    if s1 + m < 0:
        print('No')
        exit()
    s1 += t

s2 = 0
for m, t in minus:
    if s2 + m < 0:
        print('No')
        exit()
    s2 += t

if s1 == s2:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

n = int(input())

plus = []
minus = []
for _ in range(n):
    min_s = 0
    ts = 0
    s = input().strip()
    for c in s:
        ts += 1 if c == '(' else -1
        min_s = min(ts, min_s)
    if ts >= 0:
        plus.append((min_s, ts))
    else:
        min_s = 0
        ts = 0
        for c in s[::-1]:
            ts += 1 if c == ')' else -1
            min_s = min(ts, min_s)
        minus.append((min_s, ts))

plus.sort()
minus.sort()

s1 = 0
for m, t in plus:
    if s1 + m < 0:
        print('No')
        exit()
    s1 += t

s2 = 0
for m, t in minus:
    if s2 + m < 0:
        print('No')
        exit()
    s2 += t

if s1 == s2:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

def resolve():
    N = int(readline())
    S = [readline().strip() for i in range(N)]
    L,R = [],[]
    D = []
    for i in range(N):
        L_R = [0,0] #左右にどれだけ開いているか
        for i in S:
            if i == ")":
                if L_R[1] > 0 :
                    L_R[1] -= 1
                else:
                    L_R[0] +=1
            if i == "(":
                L_R[1] += 1
            if L_R[0] == 0 and L_R[1] == 0:
                pass
            elif L_R[0] == 0:
                R.append(L_R[1])
            elif L_R[1] == 0:
                L.append(L_R[0])
            else:
                D.append((L_R))
    L = sum(L)
    R = sum(R)

    inc = []
    dec = []
    for l,r in D:
        if l > r:
            inc.append((l, r))
        else:
            dec.append((l, r))
    
    inc.sort(key=lambda x:x[1])
    dec.sort(key=lambda x:-x[1])
    
    D = inc + dec
    
    for i, (l,r) in enumerate(D):
        L -= r
        if L < 0:
            print('No')
            exit(0)
        L += l
    
    if L == R:
        print('Yes')
    else:
        print('No')
resolve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n = ri()
    neg_dm = []
    pos_dm = []
    for i in range(n):
        S = input()
        depth = 0
        max_depth = 0
        for c in S:
            if c == '(':
                depth -= 1
            else:
                depth += 1
                max_depth = max(max_depth, depth)
        if depth < 0:
            neg_dm.append([max_depth, depth])
        else:
            pos_dm.append([max_depth, depth])

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

    # print (neg_dm)
    # print (pos_dm)
    curr_depth = 0
    for m, d in neg_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

    for m, d in pos_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

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


mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n = ri()
    neg_dm = []
    pos_dm = []
    for i in range(n):
        S = input()
        depth = 0
        max_depth = 0
        for c in S:
            if c == '(':
                depth -= 1
            else:
                depth += 1
                max_depth = max(max_depth, depth)
        if depth < 0:
            neg_dm.append([max_depth, depth])
        else:
            pos_dm.append([max_depth, depth])

    neg_dm.sort()
    pos_dm.sort(reverse=True)

    curr_depth = 0
    for m, d in neg_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

    for m, d in pos_dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

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


mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

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


def solve():
    n = ri()
    dm = []
    for i in range(n):
        S = input()
        depth = 0
        max_depth = 0
        for c in S:
            if c == '(':
                depth -= 1
            else:
                depth += 1
                max_depth = max(max_depth, depth)
        dm.append([max_depth, depth])

    dm.sort()
    # print (dm)
    curr_depth = 0
    for m, d in dm:
        if m > -curr_depth:
            print ("No")
            return
        curr_depth += d

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







mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
sl, sr = 0, 0
t = []

for _ in range(N):
    s = input()
    l, r = 0, 0
    q = []
    for i in s:
        if i==")":
            if q and q[-1]=="(":
                r -= 1
                q.pop()
            else:
                q.append(")")
                l += 1
        else:
            q.append("(")
            r += 1
    if r-l>=0:
        t.append((l-r, 0))
    else:
        t.append((l-r, 1))
t.sort()

if t[0][0]<=0 and t[-1][0]>=0:
    s = 0
    for i, j in t:
        s += i
    if s==0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
sl, sr = 0, 0
t = []

for _ in range(N):
    s = input()
    l, r = 0, 0
    q = []
    for i in s:
        if i==")":
            if q and q[-1]=="(":
                r -= 1
                q.pop()
            else:
                q.append(")")
                l += 1
        else:
            q.append("(")
            r += 1
    if r-l>=0:
        t.append((l-r, 0))
    else:
        t.append((l-r, 1))
t.sort()

if t[0][0]<0 and t[-1][0]>0:
    s = 0
    for i, j in t:
        s += i
    if s==0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

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

def main():
  n = int(input())
  
  a = []
  b = []
  for i in range(n):
    s = input()
    c1, c2 = 0, 0
    for i in range(len(s)):
      if s[i] == "(":
        c2 += 1
      if s[i] == ")":
        if c2:
          c2 -= 1
        else:
          c1 += 1
    if c1 >= c2:
      b.append((c2, c1))
    else:
      a.append((c1, c2))
  a.sort()
  b.sort()
  ans = False
  sub = 0
  for value in a:
    k1, k2 = value[0], value[1]
    if sub < k1:
      ans = True
      break
    sub += k2-k1
  for value in b:
    k2, k1 = value[0], value[1]
    if ans or sub < k1:
      ans = True
      break
    sub += k2-k1
  print("No" if ans or sub else "Yes")

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
sl, sr = 0, 0
t = []

for _ in range(N):
    s = input()
    l, r = 0, 0
    q = []
    for i in s:
        if i==")":
            if q and q[-1]=="(":
                r -= 1
                q.pop()
            else:
                q.append(")")
                l += 1
        else:
            q.append("(")
            r += 1
    t.append((l, r))
t.sort(key=lambda x:(-x[1], x[0]))

if t[0][0]==0 and t[-1][1]==0:
    a = t[0][1]
    for i, j in t[1:]:
        a += j
        if i>a:
            print("No")
            break
        v = min(i, a)
        a -= v
    else:
        if a==0:
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N = int(input())
sl, sr = 0, 0
t = []

for _ in range(N):
    s = input()
    l, r = 0, 0
    q = []
    for i in s:
        if i==")":
            if q and q[-1]=="(":
                r -= 1
                q.pop()
            else:
                q.append(")")
                l += 1
        else:
            q.append("(")
            r += 1
    t.append((l, r))
t.sort(key=lambda x:(-x[1], x[0]))

if t[0][0]==0 and t[-1][1]==0:
    a = t[0][1]
    for i, j in t[1:]:
        if i>a:
            print("No")
            break
        v = min(i, a)
        a -= v
    else:
        if a==0:
            print("Yes")
        else:
            print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
# bracket sequencing

import sys


def input(): return sys.stdin.readline().rstrip()


N = int(input())
data = []
for _ in range(N):
    plus = 0
    minus = 0
    sums = 0
    S = input()
    for i in range(len(S)):
        if S[i] == "(":
            sums += 1
            plus = max(plus, sums)
        else:
            sums -= 1
            minus = min(minus, sums)
    data.append((plus, minus, sums))
# dataの内部構造 = max+ ,min-, last_dif
res = 0
for x in data:
    res += x[-1]
if res != 0:
    print("No")
    sys.exit()
# res=0の条件を満たす下で考える
plus_que = []
minus_que = []
for x in data:
    if x[-1] >= 0:
        plus_que.append(x)
    else:
        minus_que.append(x)

plus_que.sort(key=lambda x: (-x[1], -x[-1]))
minus_que.sort(key=lambda x: (x[1], x[1]))
flag = True
now_value = 0
for x in plus_que:
    if now_value+x[1] < 0:
        flag = False
        break
    else:
        now_value += x[-1]

for y in plus_que:
    if now_value+y[1] < 0:
        flag = False
        break
    else:
        now_value += y[-1]
if flag:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n == 0:
        print("Yes")
        return
    slup = []
    sldown = []
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
        if height >= 0:
            slup.append([mi, height])
        else:
            sldown.append([mi-height, -height])

    slup.sort(key = lambda x: -x[0])
    sldown.sort(key = lambda x: -x[0])
    if sum([si[0] for si in slup]) + sum([-si[0] for si in sldown]):
        print("No")
        return
    h = 0
    for si in slup:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    h = 0
    for si in sldown:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    print("Yes")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    slup = []
    sldown = []
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
        if height >= 0:
            slup.append([mi, height])
        else:
            sldown.append([mi-height, -height])

    slup.sort(key = lambda x: -x[0])
    sldown.sort(key = lambda x: -x[0])
    if sum([si[0] for si in slup]) + sum([-si[0] for si in sldown]):
        print("No")
        return
    h = 0
    for si in slup:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    h = 0
    for si in sldown:
        if h+si[0] < 0:
            print("No")
            return
        h += si[1]
    print("Yes")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    slup = []
    sldown = []
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
        if height > 0:
            slup.append([mi, height])
        else:
            sldown.append([mi-height, height])

    slup.sort(key = lambda x: -x[0])
    sldown.sort(key = lambda x: -x[0])
    h = 0
    for si in slup:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0]
    slup.sort(key = lambda x: -x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0]
    slup.sort(key = lambda x: [-x[0], -x[1]])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: [-x[0], -x[1]])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    # if n%2:
    #     print("No")
    #     return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[0])
    slmiddle = [si for si in sl if si[1] >= 0 and si[0] < 0]
    slmiddle.sort(key = lambda x: x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in slmiddle:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[0])
    slmiddle = [si for si in sl if si[1] >= 0 and si[0] < 0]
    slmiddle.sort(key = lambda x: x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in slmiddle:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[1])
    slmiddle = [si for si in sl if si[1] >= 0 and si[0] < 0]
    slmiddle.sort(key = lambda x: x[0])
    sldown = [si for si in sl if si[1] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in slmiddle:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[1])
    sldown = [si for si in sl if si[1] < 0 or si[0] < 0]
    sldown.sort(key = lambda x: x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    slup.sort(key = lambda x: -x[1])
    sldown = [si for si in sl if si[1] < 0 or si[0] < 0]
    sldown.sort(key = lambda x: -x[0])
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in sldown:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    slup = [si for si in sl if si[1] >= 0 and si[0] >= 0]
    sldown = [si for si in sl if si[1] < 0 or si[0] < 0]
    h = 0
    for si in slup:
        if h < 0 :
            print("No")
            return
        h += si[1]
    for si in sldown[::-1]:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
plus=[]
minus=[]
for _ in range(N):
    S=input()
    tmp=0
    flag=True
    minus_tmp=0
    for i in range(len(S)):
        if S[i]=="(":
            tmp+=1
        else:
            tmp-=1
        if tmp<0:
            flag=False
            minus_tmp=min(minus_tmp,tmp)
    if flag:
        plus.append(tmp)
    else:
        minus.append((-tmp,-minus_tmp))

ans=sum(plus)
minus.sort(reverse=True,key=lambda x:x[1])
for i,j in minus:
    if j>ans:
        print("No")
        exit()
    ans-=i
if ans==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    slup = [si for si in sl if si[0] >= 0]
    sldown = [si for si in sl if si[0] < 0]
    h = 0
    for si in slup:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    for si in sldown[::-1]:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    if n%2:
        print("No")
        return
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    h = 0
    for si in sl:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    h = 0
    for si in sl:
        if h <= 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    sl = [None]*n
    for i in range(n):
        height, mi = 0, 0
        for si in input():
            if si == "(":
                height += 1
                mi = min(mi, height)
            else:
                height -= 1
                mi = min(mi, height)
            
        sl[i] = [mi, height]
    sl.sort(key=lambda x: -x[0])
    h = 0
    for si in sl:
        if h < 0 or h+si[0] < 0:
            print("No")
            return
        h += si[1]
    if h == 0:
        print("Yes")
    else:
        print("No")
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
  input = sys.stdin.readline
  n = int(input())
  key1 = []
  key2 = 0
  key3 = 0
  for i in range(n):
    s = input()
    c1, c2 = 0, 0
    for j in range(len(s)):
      if s[j] == "(":
        c2 += 1
      if s[j] == ")":
        if c2:
          c2 -= 1
        else:
          c1 += 1
    if c1 and c2:
      key1.append((c1, c2))
    elif c1:
      key2 += c1
    elif c2:
      key3 += c2
  key1.sort()
  judge = key2
  for value in key1:
    judge -= value[0]
    if judge < 0:
      print("No")
      sys.exit()
    judge += value[1]
  
  judge -= key3
  if judge == 0:
    print("Yes")
  else:
    print("No")

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
  input = sys.stdin.readline
  n = int(input())
  key1 = []
  key2 = 0
  key3 = 0
  for i in range(n):
    s = input()
    c1, c2 = 0, 0
    for j in range(len(s)):
      if s[j] == "(":
        c2 += 1
      if s[j] == ")":
        if c2:
          c2 -= 1
        else:
          c1 += 1
    if c1 and c2:
      key1.append((c1-c2, c1, c2))
    elif c1:
      key2 += c1
    elif c2:
      key3 += c2
  key1.sort()
  judge = key2
  for value in key1:
    judge -= value[1]
    if judge < 0:
      print("No")
      sys.exit()
    judge += value[2]
  
  judge -= key3
  if judge == 0:
    print("Yes")
  else:
    print("No")

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
zl, zr, zall = 0, 0, 0
sl, sr = 0, 0

for _ in range(N):
    s = input()
    l, r = 0, 0
    q = []
    for i in s:
        if i==")":
            if q and q[-1]=="(":
                r -= 1
                q.pop()
            else:
                q.append(")")
                l += 1
        else:
            q.append("(")
            r += 1
    sl += l
    sr += r
    if l==0 and r==0:
        zall += 1
    elif l==0:
        zl += 1
    elif r==0:
        zr += 1

if sl==sr:
    if (zl and zr) or (zall>=2):
        print("Yes")
    else:
        print("No")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n=int(input())
s=[input() for _ in range(n)]
cnt=[[0,0] for _ in range(n)]
for i in range(n):
    k=len(s[i])
    for l in range(k):
        s[i]=s[i].replace("()","")
    for j in range(len(s[i])):
        if s[i][j]=="(":
            cnt[i][1]+=1
        else:
            cnt[i][0]+=1
cnt.sort(key=itemgetter(1),reverse=True)
cnt.sort(key=itemgetter(0))
#print(s)
#print(cnt)
ok=True
cnt0,cnt1=0,0
for i in range(n):
    if cnt1<cnt0+cnt[i][0]:
        ok=False
        break
    cnt0+=cnt[i][0]
    cnt1+=cnt[i][1]
if cnt0!=cnt1:
    ok=False
if ok:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[input() for _ in range(n)]
cnt=[[0,0] for _ in range(n)]
for i in range(n):
    k=len(s[i])
    r=n-1
    for l in range(k):
        s[i]=s[i].replace("()","")
    for j in range(len(s[i])):
        if s[i][j]=="(":
            cnt[i][1]+=1
        else:
            cnt[i][0]+=1
cnt.sort()
#print(s)
#print(cnt)
ok=True
cnt0,cnt1=0,0
for i in range(n):
    if cnt1<cnt0+cnt[i][0]:
        ok=False
        break
    cnt0+=cnt[i][0]
    cnt1+=cnt[i][1]
if cnt0!=cnt1:
    ok=False
if ok:
    print("Yes")
else:
    print("No")