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():
    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])
    
    # r-1の大きい順
    ls_minus.sort(key=lambda x: x[0] - x[1], reverse=True)
    # lの小さい順
    ls_minus.sort(key=lambda x: x[0])

    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())
    ls = []
    l_0 = []
    r_0 = []
    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))
        else:
            ls.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls) == 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.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls.sort(key=lambda x: x[0])

    # rの大きい順
    l_0.sort(key=lambda x: x[1], reverse=True)
    # lの大きい順
    r_0.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)):
        # l = ls[i][0]
        r = ls[i][1]
        x = now_r - ls[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:
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
    m = []
    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: m.append((e,w))
        else: p += e
    m.sort(reverse=True)
    for e,w in m:
        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:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        level = 0
        for c in input():
            if c == '(':
                level += 1
            else:
                level -= 1
                depth = min(depth, level)
        if level > 0:
            inc_chunks.append((depth, level))
        else:
            dec_chunks.append((level - depth, -level))

    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, level in inc_chunks:
        if inc_level + depth < 0:
            return 'No'
        inc_level += level
    dec_level = 0
    for depth, level in dec_chunks:
        if dec_level + depth < 0:
            return 'No' 
        dec_level += level
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ls = []
    l_0 = []
    r_0 = []
    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))
        else:
            ls.append((left, right))
        sum_l += left
        sum_r += right

    if len(ls) == 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.sort(key=lambda x: x[1] - x[0], reverse=True)
    # lの小さい順
    ls.sort(key=lambda x: x[0])

    # rの大きい順
    l_0.sort(key=lambda x: x[1], reverse=True)
    # lの大きい順
    r_0.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)):
        l = ls[i][0]
        r = ls[i][1]
        x = now_r - l
        if x >= 0:
            now_l = now_l
            now_r = x + r
        else:
            print("No")
            return

    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((depth, final))
        else:
            dec_chunks.append((final - depth, -final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, final in inc_chunks:
        if inc_level + depth < 0:
            return 'No'
        inc_level += final
    dec_level = 0
    for depth, final in dec_chunks:
        if dec_level + depth < 0:
            return 'No' 
        dec_level += final
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((depth, final))
        else:
            dec_chunks.append((final - depth, -final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, final in inc_chunks:
        if inc_level - depth < 0:
            return 'No'
        inc_level += final
    dec_level = 0
    for depth, final in dec_chunks:
        if dec_level - depth < 0:
            return 'No' 
        dec_level += final
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:

n = int(input())
s = [list(input()) for i in range(n)]
r = []
l = []
ans = 0
for i in s:
    now = 0
    c = 0
    for j in i:
        if j =="(":
            now += 1
        else:
            now -= 1
        c = min(c,now)
    if c == 0:
        ans += now
    elif now >= 0:
        l.append([c,now])
    else:
        r.append([c,-now])

l.sort(reverse =True)
r.sort()
for i,j in l:
    if ans + i < 0:
        print("No")
        exit()
    else:
        ans += j

for i,j in r:
    if ans+i < 0:
        print("No")
        exit()
    else:
        ans -= j
if ans == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ls = []
    l_0 = False
    r_0 = False
    sum_l = 0
    sum_r = 0
    dic = {}
    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

        ls.append((left, right))
        if left == 0:
            l_0 = True
        if right == 0:
            r_0 = True
        sum_l += left
        sum_r += right
        cnt = dic.setdefault((left, right), 0)
        dic[(left, right)] = cnt + 1

    if len(ls) == 0:
        print("Yes")
        return

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

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

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

    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((-depth, final))
        else:
            dec_chunks.append((final - depth, -final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    inc_level = 0
    for depth, final in inc_chunks:
        if inc_level - depth < 0:
            return 'No'
        inc_level += final
    dec_level = 0
    for depth, final in dec_chunks:
        if dec_level - depth < 0:
            return 'No' 
        dec_level += final
    if inc_level != dec_level:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
from itertools import chain


Par = namedtuple("Par", ["bottom", "delta"])


def parse(s) -> Par:
    bottom = 0
    delta = 0
    for c in s:
        delta += 1 if c == "(" else -1
        bottom = min(bottom, delta)
    return Par(bottom=bottom, delta=delta)


def compute(pars):
    h = 0
    for par in pars:
        if h + par.bottom < 0:
            return None
        h += par.delta
    return h


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

    incs = []
    decs = []
    for _ in range(N):
        par = parse(input())
        if par.delta > 0:
            incs.append(par)
        else:
            # look from right side
            # i.e. move origin to delta
            decs.append(Par(bottom=par.bottom-par.delta, delta=-par.delta))
    # sort by bottom in descending order
    incs.sort(key=lambda p: p.bottom, reverse=True)
    decs.sort(key=lambda p: p.bottom, reverse=True)

    inc_tot = compute(incs)
    dec_tot = compute(decs)
    if inc_tot and dec_tot and inc_tot == dec_tot:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
from itertools import chain


Par = namedtuple("Par", ["bottom", "delta"])


def parse(s) -> Par:
    bottom = 0
    delta = 0
    for c in s:
        delta += 1 if c == "(" else -1
        bottom = min(bottom, delta)
    return Par(bottom=bottom, delta=delta)


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

    incs = []
    decs = []
    for _ in range(N):
        par = parse(input())
        if par.delta > 0:
            incs.append(par)
        else:
            decs.append(par)
    # sort by bottom in descending order
    incs.sort(key=lambda p: p.bottom, reverse=True)
    decs.sort(key=lambda p: p.bottom)

    total = 0
    for bottom, delta in chain(incs, decs):
        if total + bottom < 0:
            print("No")
            return
        total += delta
    print("Yes" if total == 0 else "No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((-depth, final))
        else:
            dec_chunks.append((final, -depth))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort()

    level = 0
    for depth, final in inc_chunks:
        if level - depth < 0:
            return 'No'
        level += final
    for final, depth in dec_chunks:
        if level - depth < 0:
            return 'No' 
        elif level - final < 0:
            return 'No'
        level += final
    if level != 0:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
B1 = []
B2 = []

def change(S):
    MIN = 0
    SUM = 0
    for i in S:
        if i == ')':
            SUM -= 1
            MIN = min(MIN, SUM)
        else:
            SUM += 1
    MIN *= -1
    return (MIN, SUM)

for _ in range(N):
    b = change(input())
    if b[1] > 0:
        B1.append(b)
    else:
        B2.append(b)

B1.sort()
B2.sort(reverse = True)

cnt = 0
for b in B1:
    if cnt < b[0]:
        print('No')
        sys.exit()
    cnt += b[1]

for b in B2:
    if cnt < b[0]:
        print('No')
        sys.exit()
    cnt += b[1]

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

Submission status: Wrong Answer

Solution code:
from collections import namedtuple
from itertools import chain


Par = namedtuple("Par", ["bottom", "delta"])


def parse(s) -> Par:
    bottom = 0
    delta = 0
    for c in s:
        delta += 1 if c == "(" else -1
        bottom = min(bottom, delta)
    return Par(bottom=bottom, delta=delta)


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

    incs = []
    decs = []
    for _ in range(N):
        par = parse(input())
        if par.delta > 0:
            incs.append(par)
        else:
            decs.append(par)
    # sort by bottom in descending order
    incs.sort(key=lambda p: p.bottom, reverse=True)
    decs.sort(key=lambda p: p.bottom, reverse=True)

    total = 0
    for bottom, delta in chain(incs, decs):
        if total + bottom < 0:
            print("No")
            return
        total += delta
    print("Yes" if total == 0 else "No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ls = []
    l_0 = False
    r_0 = False
    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

        ls.append((left, right))
        if left == 0:
            l_0 = True
        if right == 0:
            r_0 = True
        sum_l += left
        sum_r += right

    if len(ls) == 0:
        print("Yes")
        return

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

    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
sp, sm = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, tmp = 0, 0
    for i in range(m):
        if s[i] == ')':
            tmp -= 1
        else:
            tmp += 1
        l = min(l, tmp)

    res += tmp
    if tmp >= 0:
        sp.append((l, tmp))
    else:
        sm.append((l, tmp))

if res != 0:
    print('No')
    exit()

sp.sort(key=lambda x: -x[0])
sm.sort(key=lambda x: x[0])

flg = True
s = sp + sm
x = len(s)
cur = 0
for i in range(x):
    l, tmp = s[i]
    if cur + l < 0:
        flg = False
        break
    cur += tmp

if flg:
    print('Yes')

else:
    print('No')

Submission status: Wrong Answer

Solution code:
def parse(s):
    bottom = float("inf")
    delta = 0
    for c in s:
        delta += 1 if c == "(" else -1
        bottom = min(bottom, delta)
    return bottom, delta


def main():
    N = int(input())
    pars = list(map(parse, (input() for _ in range(N))))

    incs = [p for p in pars if p[1] > 0]
    incs = sorted(incs, key=lambda p: p[0], reverse=True)
    decs = [p for p in pars if p[1] <= 0]
    decs = sorted(decs, key=lambda p: p[0], reverse=True)

    from itertools import chain

    val = 0
    for bottom, delta in chain(incs, decs):
        if val + bottom < 0:
            print("No")
            return
        val += delta
    if val == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
sp, sm = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, tmp = 0, 0
    for i in range(m):
        if s[i] == ')':
            tmp -= 1
        else:
            tmp += 1
        l = min(l, tmp)

    res += tmp
    if tmp >= 0:
        sp.append((l, tmp))
    else:
        sm.append((l, tmp))

if res != 0:
    print('No')
    exit()

sp.sort(key=lambda x: -x[0])
sm.sort(key=lambda x: -x[0])

flg = True
s = sp + sm
x = len(s)
cur = 0
for i in range(x):
    l, tmp = s[i]
    if cur + l < 0:
        flg = False
        break
    cur += tmp

if flg:
    print('Yes')

else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((-depth, final))
        else:
            dec_chunks.append((-depth, -final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    level = 0
    for depth, final in inc_chunks:
        if level - depth < 0:
            return 'No'
        level += final
    for depth, final in dec_chunks:
        if level - depth < 0:
            return 'No' 
        elif level - final < 0:
            return 'No'
        level -= final
    if level != 0:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:



def main():
    n = int(input())
    ls = []
    l_0 = False
    r_0 = False
    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

        ls.append((left, right))
        if left == 0:
            l_0 = True
        if right == 0:
            r_0 = True
        sum_l += left
        sum_r += right

    if len(ls) ==0:
        print("Yes")
        return

    if not l_0 and not r_0:
        print("No")
        return
    if sum_l != sum_r:
        print("No")
        return

    print("Yes")


main()

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((-depth, final))
        else:
            dec_chunks.append((-depth, -final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    level = 0
    for depth, final in inc_chunks:
        if level - depth < 0:
            return 'No'
        level += final
    for depth, final in dec_chunks:
        if level - depth < 0:
            return 'No' 
        level -= final
    if level != 0:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
def parse(s):
    bottom = float("inf")
    delta = 0
    for c in s:
        delta += 1 if c == "(" else -1
        bottom = min(bottom, delta)
    return bottom, delta


def main():
    N = int(input())
    pars = list(map(parse, (input() for _ in range(N))))

    incs = [p for p in pars if p[1] > 0]
    incs = sorted(incs, key=lambda p: p[0], reverse=True)
    decs = [p for p in pars if p[1] <= 0]

    from itertools import chain

    val = 0
    for bottom, delta in chain(incs, decs):
        if val + bottom < 0:
            val = -1
            break
        val += delta
    if val == 0:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


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


def solve():
    N = int(input())
    inc_chunks = []
    dec_chunks = []
    for _ in range(N):
        depth = 0
        final = 0
        for c in input():
            if c == '(':
                final += 1
            else:
                final -= 1
                depth = min(depth, final)
        if depth >= 0 and final == 0:
            continue
        if final > 0:
            inc_chunks.append((-depth, final))
        else:
            dec_chunks.append((-depth, final))
    inc_chunks.sort(reverse=True)
    dec_chunks.sort(reverse=True)
    level = 0
    for depth, final in inc_chunks:
        if level - depth < 0:
            return 'No'
        level += final
    for depth, final in dec_chunks:
        if level - depth < 0:
            return 'No' 
        level += final
    if level != 0:
        return 'No'
    return 'Yes'


print(solve())

Submission status: Wrong Answer

Solution code:
# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append([min_state, state])
    else:
        
        list_minus.append([min_state - state, -state])

def compute(arr):
    total_state = 0
    for min_state, state in list_plus[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')

Submission status: Wrong Answer

Solution code:
n = int(input())
lr1, lr2 = [], []
res = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, r = 0, 0
    tmp = 0
    for i in range(m):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        l = max(l, tmp)
    tmp = 0
    for i in range(m):
        if s[m-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        r = max(r, tmp)

    res += r - l
    if r - l >= 0:
        lr1.append((l, r))
    else:
        lr2.append((l, r))

if res != 0:
    print('No')
    exit()

lr1.sort(key=lambda x: -x[0])
lr2.sort(key=lambda x: -x[1])

flg1, flg2 = True, True

n1, n2 = len(lr1), len(lr2)
tmp = 0
for i in range(n1):
    l, r = lr1[i]
    tmp -= l
    if tmp < 0:
        flg1 = False
    tmp += r

tmp = 0
for i in range(n2):
    l, r = lr2[i]
    tmp -= r
    if tmp < 0:
        flg2 = False
    tmp += l

if flg1 and flg2:
    print('Yes')

else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
lr1, lr2 = [], []
flg = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, r = 0, 0
    tmp = 0
    for i in range(m):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        l = max(l, tmp)
    tmp = 0
    for i in range(m):
        if s[m-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        r = max(r, tmp)

    if r - l >= 0:
        lr1.append((l, r))
    else:
        lr2.append((l, r))

lr1.sort(key=lambda x: -x[0])
lr2.sort(key=lambda x: -x[1])
lr = lr1 + lr2[::-1]
#print(lr)

x = len(lr)
check = True
tmp = 0
for i in range(x):
    l, r = lr[i]
    tmp -= l
    if tmp < 0:
        check = False
        break
    tmp += r
if tmp != 0:
    check = False

tmp = 0
for i in range(x):
    l, r = lr[x-1-i]
    tmp -= r
    if tmp < 0:
        check = False
        break
    tmp += l
if tmp != 0:
    check = False

if check:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
n = int(input())
lr1, lr2 = [], []
flg = 0
for _ in range(n):
    s = input()
    m = len(s)

    l, r = 0, 0
    tmp = 0
    for i in range(m):
        if s[i] == ')':
            tmp += 1
        else:
            tmp -= 1
        l = max(l, tmp)
    tmp = 0
    for i in range(m):
        if s[m-1-i] == '(':
            tmp += 1
        else:
            tmp -= 1
        r = max(r, tmp)

    if r - l >= 0:
        lr1.append((l, r))
    else:
        lr2.append((l, r))

lr1.sort(key=lambda x: -x[0])
lr2.sort(key=lambda x: -x[1])
lr = lr1 + lr2[::-1]
#print(lr)

x = len(lr)
check = True
tmp = 0
for i in range(x):
    l, r = lr[i]
    tmp -= l
    if tmp < 0:
        check = False
        break
    tmp += r
if tmp != 0:
    check = False

if check:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    pos = []
    neg = []
    for i in range(N):
        tmp = 0
        b = 0
        for c in sr():
            if c == '(':
                tmp += 1
            else:
                tmp -= 1
                b = min(b, tmp)
        if tmp > 0:
            pos.append([tmp, b])
        else:
            neg.append([tmp, b])
    pos = sorted(pos, key=lambda x: (x[1], x[0]))[::-1]
    neg = sorted(neg, key=lambda x: (x[1], x[0]))
    c = 0
    for p in pos:
        t, b = p
        if c+b < 0:
            print('No')
            return
        c += t
    for n in neg:
        t, b = n
        if c+b < 0:
            print('No')
            return
        c += t
    if c == 0:
        print('Yes')
    else:
        print('No')
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N = ir()
    pos = []
    neg = []
    for i in range(N):
        tmp = 0
        b = 0
        for c in sr():
            if c == '(':
                tmp += 1
            else:
                tmp -= 1
                b = min(b, tmp)
        if tmp > 0:
            pos.append([tmp, b])
        else:
            neg.append([tmp, b])
    pos = sorted(pos, key=lambda x: (x[1], x[0]))[::-1]
    neg = sorted(neg, key=lambda x: (x[1], x[0]))
    c = 0
    for p in pos:
        t, b = p
        if c+b < 0:
            print('No')
            return
        c += t
    for n in neg:
        t, b = n
        if c+b < 0:
            print('No')
            return
        c += t
    if c == 0:
        print('Yes')
    else:
        print('No')
#resolve()