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, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    s = [list(input()) for _ in range(n)]
    cnt = [[0,0] for _ in range(n)]
    for i in range(n):
        t = s[i]
        flag = 0
        l = 0
        r = 0
        for j in range(len(t)):
            if not flag and t[j] == ')':
                r += 1
            elif t[j] == '(':
                flag = 1
                l += 1
            else:
                l -= 1
                if l == 0:
                    flag = 0
        cnt[i] = [l,r]
    flag1 = 0
    flag2 = 0
    L,R = 0,0
    for i in range(n):
        if cnt[i][0] == 0 and cnt[i][1] != 0:
            flag1 = 1
        if cnt[i][1] == 0 and cnt[i][0] != 0:
            flag2 = 1
        L += cnt[i][0]
        R += cnt[i][1]
    if flag1 and flag2 and (L==R):
        print('Yes')
    else:
        print('No')
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
br = [input().rstrip() for i in range(n)]
ls = []
numsum = 0
charge = 0
for i in range(n):
  s = br[i]
  need = 0
  num = 0
  for t in s:
    if t == "(":
      num += 1
    else:
      num -= 1
    need = max(need,-num)
  numsum += num
  if need == 0:
    charge += num
  else:
    ls.append((need,num))
if numsum != 0:
  print("No")
  exit()
ls.sort()
l = len(ls)
vis = [0]*l
for i,x in enumerate(ls):
  need,num = x
  if need <= charge and num >= 0:
    vis[i] = 1
    charge += num
for i in range(l)[::-1]:
  if vis[i]:
    continue
  need,num = ls[i]
  if need > charge:
    print("No")
    exit()
  charge += num
print("Yes")

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
if n==1:
    t=s[0]
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:
        print('Yes')
    else:
        print('No')
    exit()
f=g=h=a=b=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    if x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if (h > 1 or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

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

A = [[], [], []]

u = 0

for i in range(n):
    a = 0
    b = 0
    for j in range(len(S[i])):
        if S[i][j] == "(":
            a += 1
        else:
            a -= 1
            b = min(b, a)
    u += a
    if a > 0:
        A[0].append([b, a])
    elif a == 0:
        A[1].append([b, a])
    else:
        A[2].append([b, a])


# print(A)

if u != 0:
    print("No")
    sys.exit()

A[0].sort(reverse=True)
A[2].sort()

ng = 0
a = 0
for i in range(len(A[0])):
    a += A[0][i][0]
    if a < 0:
        ng = 1
        break
    a += A[0][i][1]-A[0][i][0]
    if a < 0:
        ng = 1
        break

if ng == 0:
    for i in range(len(A[1])):
        a += A[1][i][0]
        if a < 0:
            ng = 1
            break
        a -= A[1][i][0]

if ng == 0:
    for i in range(len(A[2])):
        a += A[2][i][0]
        if a < 0:
            ng = 1
            break
        a += A[2][i][1]-A[2][i][0]
        if a < 0:
            ng = 1
            break

if ng == 1:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
increasing = []
decreasing = []
for _ in range(n):
    s = input().rstrip()
    minima = 0
    fin = 0
    for ch in s:
        if ch == ")":
            fin -= 1
            if fin < minima:
                minima = fin
        else:
            fin += 1
    if fin >= 0:
        increasing.append((minima, fin))
    else:
        decreasing.append((minima, fin))

increasing.sort(reverse=True)
decreasing.sort(reverse=True)

current = 0
for minima, diff in increasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
for minima, diff in decreasing:
    if current + minima < 0:
        print("No")
        exit()
    current += diff
if current != 0:
    print("No")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
import sys
mx = 10**6+5
index_plus = [[] for _ in range(mx*2)]
index_minus = [[] for _ in range(mx*2)]
n = int(input())
s = [input() for _ in range(n)]
cnts = []
mins = []
sm = 0
cnt_minus = 0
cnt_plus = 0
for i in range(n):
    cnt = 0
    mn = 0
    for c in s[i]:
        if c == '(':
            cnt+=1
        else: cnt-=1
        mn = min(cnt, mn)
    cnts.append(abs(cnt))
    mins.append(abs(mn))
    sm+=cnt
    if cnt<0:
        index_minus[mn].append(i)
        cnt_minus+=1
    else:
        index_plus[-mn].append(i)
        cnt_plus+=1
if(sm != 0):
    print('No')
    sys.exit()
now = 0
que = []
for i in range(-mx, now+1):
    for j in index_plus[i]:
        que.append(j)
for i in range(cnt_plus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_plus[k]:
            que.append(k)
    now+=cnts[j]

index_plus = index_minus
que = []
now = 0
for i in range(-mx, now+1):
    for j in index_plus[i]:
        que.append(j)
for i in range(cnt_minus):
    if(len(que)==0):
        print('No')
        sys.exit()
    j = que.pop()
    for k in range(now+1, now+cnts[j]+1):
        for l in index_plus[k]:
            que.append(k)
    now+=cnts[j]
print('Yes')

Submission status: Wrong Answer

Solution code:
n=int(input())
ch=True
sm=0
for t in range (n):
    s=input()
    l=len(s)
    i=0
    curr=0
    m=l+1
    for i in range (l):
        if s[i]=='(':
            curr+=1
        else:
            curr-=1
        m=min(m,curr)
    if m<curr and m<0:
        ch=False
    sm+=curr
    #print(m,curr,ch)
if ch and sm==0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import heapq
n = int(input())
s = [input() for _ in range(n)]
t = [None] * n
for i in range(n):
    k = 0
    m = 0
    for c in s[i]:
        if c == '(':
            k += 1
        else:
            k -= 1
            m = min(k, m)
    t[i] = (-m, k)
t.sort()
hq = []
d = 0
idx = 0
for i in range(n):
    while idx < n and d >= t[idx][0]:
        m, k = t[idx]
        heapq.heappush(hq, k)
        idx += 1
    if hq:
        k = heapq.heappop(hq)
    else:
        print('No')
        break
    d += k
else:
    if d == 0:
        print('Yes')
    else:
        print('No')

Submission status: Wrong Answer

Solution code:
N = int(input())
Ss = []
for _ in range(N):
    S = input()
    min_d = 1e100
    tot_o = 0
    tot_c = 0
    for c in S:
        if c == "(":
            tot_o += 1
        else:
            tot_c += 1
            min_d = min(min_d, tot_o - tot_c)
    Ss.append((min_d, tot_o, tot_c))
Ss.sort(reverse=True)
d = 0
for min_d, tot_o, tot_c in Ss:
    if d + min_d < 0:
        d = -1
        break
    d += tot_o - tot_c
if d == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:

"""

大事な要素
深さと高低差
まず、高低差の話が0であることは必須

もう一つ、現状が深さ以上ないと設置できない。
まず、高くするやつで置けるやつはどんどんおいていい。
置いたもん勝ち
→つまり、+で深さが浅い順においていけばいい

降りるときは、深い→浅いが置けない場合で浅い→深いが置ける場合はない
→深い順に億


"""


N = int(input())

ans = 0

pl_d = [] 
mi_d = []

for i in range(N):

    S = input()

    now = 0
    dep = 0
    mindep = 0

    for i in S:
        if i == "(":
            now += 1
            dep += 1
        else:
            now -= 1
            dep -= 1

        mindep = min(dep,mindep)

    if now >= 0:
        pl_d.append([mindep,now])
    else:
        mi_d.append([mindep,now])

pl_d.sort()
mi_d.sort()
mi_d.reverse()

d_p = pl_d + mi_d

now = 0

import sys
for i in range(N):

    nd,np = d_p[i]

    if now + nd < 0:
        print ("No")
        sys.exit()

    now += np

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip() for _ in range(N)]
pq = []
for st in S:
    m = s = 0
    for c in st:
        if c == '(':
            s += 1
        else:
            s -= 1
            m = min(m, s)
    sign = 1 if s > 0 else (0 if s == 0 else -1)
    if s > 0:
        heappush(pq, (-1, -m, s)) # take larger mins first
    elif s == 0:
        heappush(pq, (0, m, s)) # the order doesn't matter
    else:
        heappush(pq, (1, m, s)) # take the smaller mins first
num = 0
while pq:
    sign, m, s = heappop(pq)
    if sign < 0:
        m = -m
    if num + m < 0:
        print('No')
        exit()
    num += s
if num == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n = ni()
l = [ns() for _ in range(n)]
gu = list()
gd = list()
c = 0
for i in range(n):
    s = l[i]
    t = 0
    m = 0
    for x in s:
        if x == '(':
            t += 1
        else:
            t -= 1
            if m > t:
                m = t
    c += t
    if t > 0:
        gu.append((m, -t))
    else:
        gd.append((m, -t))
if c != 0:
    print('No')
    exit(0)
gu.sort()
gd.sort()
cur = 0
for m, t in gu + gd:
    if cur + m < 0:
        print('No')
        exit(0)
    cur -= t
print('Yes')

Submission status: Wrong Answer

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

a = []
b = []
ss = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    if s >= 0:
        a.append([mi, ma, s, i])
    else:
        b.append([mi, ma, s, i])
    ss += s

if ss != 0:
    print("No")
    exit()
a.sort(key=lambda x: x[0] * 100000000 - x[2])
b.sort(reverse=1, key=lambda x: x[2] * 100000000 - x[0])
s = 0
for _, _, _, i in a + b:
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        if s < 0:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

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

N = int(input())
ss = [input().replace("\n", "") for _ in range(N)]


def calc(S):
    tmp = 0
    MIN = 0
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        MIN = min(tmp, MIN)

    return MIN, tmp


cnts = []
for s in ss:
    cnts.append((*calc(s), s))


cnts.sort(reverse=True)

tmp = 0
for _, _, S in cnts:
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1

        if tmp < 0:
            print("No")
            sys.exit()


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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    left = 0
    right = 0
    left_ = 0
    right_ = 0
    for _ in range(N):
        S = input()
        stack = 0
        n_pop = 0
        for s in S:
            if s == "(":
                stack += 1
            elif stack > 0:
                stack -= 1
                n_pop += 1

        l = stack
        r = len(S) - 2 * n_pop - stack
        if l == 0:
            right += len(S) - 2 * n_pop
        elif r == 0:
            left += l
        else:
            left_ += l
            right_ += r

    left -= right_
    right -= left_
    if left >= 0 and right >= 0 and left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))
    tmp.sort(reverse=True)
    #print(tmp)
    cur = 0
    for mn, cnt in tmp:
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt
    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
lol = {}
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    if mimi not in lol:
        lol[mimi] = []
    lol[mimi].append(b)
    sas += b
if sas:
    print('No')
    exit(0)
uka = {}
for x in lol:
    lol[x].sort(reverse=True)
    uka[x] = 0
b = 0
for _ in range(n):
    f = 0
    for kek in range(-b, -b + 20202):
        if kek in lol and uka[kek] != len(lol[kek]):
            b += lol[kek][uka[kek]]
            uka[kek] += 1
            f = 1
            break
    if f == 0:
        print('No')
        exit(0)
print('Yes')

Submission status: Wrong Answer

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

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

def canFirst(S):
    now = 0
    ret = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        if now < 0:
            ret = min(ret, now)
    return ret

H = []
P = []
L = []

for s in S:
    c = canFirst(s)
    if c > 0:
        H.append(s)
    else:
        L.append((-c, s))

L.sort(reverse=True)
L = [s for _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = len(ans) - l

print('Yes' if canFirst(ans) >= 0 and (l == r) else 'No')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
br = [input().rstrip() for i in range(n)]
ls = []
numsum = 0
charge = 0
for i in range(n):
  s = br[i]
  need = 0
  num = 0
  for t in s:
    if t == "(":
      num += 1
    else:
      num -= 1
    need = max(need,-num)
  numsum += num
  if need == 0:
    charge += num
  else:
    ls.append((need,num))
if numsum != 0:
  print("No")
  exit()
ls.sort()
l = len(ls)
vis = [0]*l
for i,x in enumerate(ls):
  need,num = x
  if need <= charge and num >= 0:
    vis[i] = 1
    charge += num
for i in range(l)[::-1]:
  if vis[i]:
    continue
  need,num = ls[i]
  if need > charge:
    print("No")
    exit()
  charge -= num
print("Yes")

Submission status: Wrong Answer

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

a = []
b = []
ss = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    if s >= 0:
        a.append([mi, ma, s, i])
    else:
        b.append([mi, ma, s, i])
    ss += s

if ss != 0:
    print("No")
    exit()
a.sort(key=lambda x: x[0] * 10000000 - x[2])
b.sort(reverse=1, key=lambda x: x[0] * 10000000 - x[2])
s = 0
for _, _, _, i in a + b:
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        if s < 0:
            print("No")
            exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=a=b=0
if n==1:
    t=s[0]
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:
        print('Yes')
    else:
        print('No')
    exit()

for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    elif x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if (h > 1 or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

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

pm = 0
for s_ in s:
    pm += s_.count('(') - s_.count(')')
if pm != 0:
    print("No")
    exit()

def cap_left(s_):
    cap = 0
    stack = 0
    for x in s_:
        if x == ')':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]

s_tuple = [cap_left(s_) for s_ in s]
s_gain = list(filter(lambda x:x[1] > 0,s_tuple))
s_gain.sort(key = (lambda x: x[0]))
s_not_gain = list(filter(lambda x:x[1] <= 0,s_tuple))
s_not_gain.sort(key = (lambda x: x[0]),reverse=True)

score = 0
for s_ in s_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]
for s_ in s_not_gain:
    if score < s_[0]:
        print("No")
        exit()
    score += s_[1]

print("Yes")

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XY_pos = []
    XY_neg = []
    balance = 0
    for _ in range(N):
        S = input().rstrip('\n')
        st = []
        for s in S:
            if s == "(":
                st.append(s)
            else:
                if st:
                    if st[-1] == "(":
                        st.pop()
                    else:
                        st.append(s)
                else:
                    st.append(s)
        x = y = 0
        for s in st:
            if s == "(":
                y += 1
            else:
                x += 1
        balance += x - y
        if x > y:
            XY_neg.append((x, y))
        else:
            XY_pos.append((x, y))
    if balance:
        print("No")
        exit()

    XY_pos.sort(key=lambda p: p[0])
    val = 0
    for x, y in XY_pos:
        if x > val:
            print("No")
            #print(x, y, val)
            exit()
        val += y - x
    XY_neg.sort(key=lambda p: p[0], reverse=True)
    for x, y in XY_neg:
        if x > val:
            print("No")
            #print(x, y, val)
            exit()
        val += y - x
    print("Yes")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MAX = 10**6
N = int(input())
Ss = [input().rstrip() for _ in range(N)]

def calc(S):
    stack = []
    for s in S:
        if s == ")" and stack and stack[-1] == "(":
            stack.pop()
        else:
            stack.append(s)
    le = 0
    ri = 0
    for s in stack:
        if s == ")":
            le += 1
        else:
            ri += 1
    return le, ri

Ps = [[] for _ in range(MAX+1)]
for S in Ss:
    le, ri = calc(S)
    Ps[le].append(ri)

T = 0
ok = True
for le, P in enumerate(Ps):
    if T < len(P)*le:
        ok = False
        break
    else:
        T -= len(P)*le
        T += sum(P)

if T != 0:
    ok = False
print("Yes" if ok else "No")

Submission status: Wrong Answer

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

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

def canFirst(S):
    now = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        if now < 0:
            return False
    return True

H = []
P = []
L = []

for s in S:
    if canFirst(s):
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append(s)
        else:
            L.append((r, s))

L.sort(reverse=True)
L = [s for _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = len(ans) - l

print('Yes' if canFirst(ans) and (l == r) else 'No')

Submission status: Wrong Answer

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

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

def canFirst(S):
    now = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        if now < 0:
            return False
    return True

H = []
P = []
L = []

for s in S:
    if canFirst(s):
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append(s)
        else:
            L.append((r - l, s))

L.sort()
L = [s for _, s in L]

ans = ''.join(H + P + L)
l = ans.count('(')
r = len(ans) - l

print('Yes' if canFirst(ans) and (l == r) else 'No')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    A.append((mimi, b))
    sas += b
if sas:
    print('No')
    exit(0)
A.sort(key=lambda x: (-x[0], -x[1]))
a = 0
b = 0
for x, y in A:
    if x + b < 0:
        print('No')
        exit(0)
    a += x
    b += y
print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    A.append((mimi, b))
    sas += b
if sas:
    print('No')
    exit(0)
A.sort(key=lambda x: (x[0], - x[1]))
a = 0
b = 0
for x, y in A:
    if x + b < 0:
        print('No')
        exit(0)
    a += x
    b += y
print('Yes')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n = int(input())
    S = [None] * n
    for i in range(n):
        balance = min_balance = 0
        for c in input():
            if c == '(':
                balance += 1
            else:
                balance -= 1
            min_balance = min(min_balance, balance)
        S[i] = (min_balance, balance)
    S.sort()

    candidate = []
    now = 0
    for _ in range(n):
        while S and S[-1][0] + now >= 0:
            min_balance, balance = S.pop()
            heappush(candidate, -balance)
        if not candidate:
            print("No")
            return
        balance = -heappop(candidate)
        now += balance
        if now < 0:
            print("No")
            return

    print("Yes" if now == 0 else "No")
resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    A.append((mimi, b))
    sas += b
if sas:
    print('No')
    exit(0)
A.sort(key=lambda x: ((x[0] == 0) * -10**7)- x[1])
a = 0
b = 0
for x, y in A:
    if x + b < 0:
        print('No')
        exit(0)
    a += x
    b += y
print('Yes')

Submission status: Wrong Answer

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

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

def canFirst(S):
    now = 0
    for s in S:
        if s == '(':
            now += 1
        else:
            now -= 1
        if now < 0:
            return False
    return True

H = []
P = []
L = []

for s in S:
    if canFirst(s):
        H.append(s)
    else:
        l = s.count('(')
        r = len(s) - l
        if l >= r:
            P.append(s)
        else:
            L.append(s)

ans = ''.join(H + P + L)
l = ans.count('(')
r = len(ans) - l

print('Yes' if canFirst(ans) and (l == r) else 'No')

Submission status: Wrong Answer

Solution code:
n,*s=open(0)
n=int(n)
f=g=h=0
a=b=0
for t in s:
    c=l=r=d=0
    for u in t[:-1]:
        if u=='(':
            if d<0:d=0
            d+=1
            r+=1
        else:
            d-=1
            if d>=0:c+=1
            l+=1
    x=r-c
    y=l-c
    if x==y==0:h+=1
    elif x==0:f=1
    elif y==0:g=1
    a+=x
    b+=y
if (h > 1 or f and g) and a==b:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    A.append((mimi, b))
    sas += b
if sas:
    print('No')
    exit(0)
A.sort(key=lambda x: (x[0] == 0) * -10**7- x[1])
a = 0
b = 0
for x, y in A:
    if x < -b:
        print('No')
        exit(0)
    a += x
    b += y
print('Yes')

Submission status: Wrong Answer

Solution code:
n=int(input())
stack=[]
left=[]
for i in range(n):
    s=input()
    for i in s:
        if i=="(":
            stack.append(i)
        elif i==")" and len(stack)>0:
            stack.pop()
        else:
            left.append(i)
if len(stack)>0:
    for i in left:
        if i=="(":
            stack.append(i)
        elif i==")" and len(stack)>0:
            stack.pop()
    if len(stack)>0:
        print("No")
    else:
        print("Yes")
else:
    print("Yes")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    s = input()
    x = 0
    y = 0
    for c in s:
        if c == '(':
            y += 1
        else:
            if y >= 1:
                y -= 1
            else:
                x += 1
    a.append([y-x, x, y])
a = sorted(a)[::-1]

res = 0
for z, x, y in a:
    if x <= res:
        res = res-x+y
    else:
        res = -1
        break

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
sas = 0
for i in range(n):
    s = input()
    b = 0
    mimi = 0
    for c in s:
        if c == '(':
            b += 1
        else:
            b -= 1
        mimi = min(mimi, b)
    A.append((mimi, b))
    sas += b
if sas:
    print('No')
    exit(0)
A.sort(key=lambda x: (x[0] == 0) * -10**18 - b)
a = 0
b = 0
for x, y in A:
    if x < -b:
        print('No')
        exit(0)
    a += x
    b += y
print('Yes')

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    s = input()
    x = 0
    y = 0
    for c in s:
        if c == '(':
            y += 1
        else:
            if y >= 1:
                y -= 1
            else:
                x += 1
    a.append([x, y])
a = sorted(a)
res = 0
for x, y in a:
    if x <= res:
        res = res-x+y
    else:
        res = -1
        break

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
C = []
for i in range(N):
  A.append(input())
  B.append(A[i].count("("))
  C.append(A[i].count(")"))
  print(B[i]-C[i])

Submission status: Wrong Answer

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

pm = 0
for s_ in s:
    pm += s_.count('(') - s_.count(')')
if pm != 0:
    print("No")
    exit()

def cap_left(s_):
    cap = 0
    stack = 0
    for x in s_:
        if x == ')':
            stack -= 1
            cap = max(cap,-stack)
        else:
            stack += 1
    return [cap,stack]

s_tuple = [[s_] + cap_left(s_) for s_ in s]
s_gain = list(filter(lambda x:x[2] >= 0,s_tuple))
s_gain.sort(key = (lambda x: x[1]))
s_not_gain = list(filter(lambda x:x[2] < 0,s_tuple))
s_not_gain.sort(key = (lambda x: x[1]*1000000+x[2]),reverse=True)

score = 0
for s_ in s_gain:
    if score < s_[1]:
        print("No")
        exit()
    score += s_[2]
for s_ in s_not_gain:
    if score < s_[1]:
        print("No")
        exit()
    score += s_[2]

print("Yes")

Submission status: Wrong Answer

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

N = int(input())
ss = [input().replace("\n", "") for _ in range(N)]


def calc(S):
    tmp = 0
    MIN = 0
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        MIN = min(tmp, MIN)

    return MIN


cnts = []
for s in ss:
    cnts.append((calc(s), s))


cnts.sort(reverse=True)


tmp = 0
for c, S in cnts:
    for s in S:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1

        if tmp < 0:
            print("No")
            sys.exit()


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

Submission status: Time Limit Exceeded

Solution code:
def score(a,b):
    if b-a >= 0:
        return a
    else:
        return 10**6+1-b

N = int(input())

A = [0]*N
B = [0]*N

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

        if S[-j-1] == '(':
            b += 1
        else:
            b -= 1
        B[i] = max(B[i],b)

#print('S',S)
#print('A',A)
#print('B',B)

L = sorted(list(range(N)),key = lambda i:score(A[i],B[i]))

SA = 0
SB = 0

#print('L',L)

for i in range(N):
    if SB > A[L[i]]:
        SB += B[L[i]] - A[L[i]]
    else:
        SA += A[L[i]]-SB
        SB = B[L[i]]
    #print(SA,SB)

if SA == 0 and SB == 0:
    print('Yes')
else:
    print('No')