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 numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.zeros((N,2), dtype='int16')
    for i in range(N):
        string = input()
        m = 0
        s = 0
        for c in string:
            if c == '(':
                s += 1
            else:
                s -= 1
                m = max(m, -s)
        A[i] = [m,s]
    
    A = A[np.argsort(A[:,1])]
    A = A[np.argsort(A[:,0])][::-1]
    #print(A)
    s = 0
    while len(A) > 0:
        index = np.where(A[:,0] >= s)[0]
        if len(index) <= 0:
            print('No')
            return
        s += A[index][0][1]
        A = np.delete(A, index[0], 0)
    
    print('Yes')

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    s = S()
    ret = 0
    ret2 = 0
    for i in s:
        if ret and i == ')':
            ret -= 1
        elif i == '(':
            ret += 1
        else:
            ret2 += 1
    if ret2 > ret:
        plus += [(ret2, ret)]
    else:
        minus += [(ret2, ret)]


plus.sort(key=lambda x:x[0])
minus.sort(key=lambda x:x[1], reverse=True)

ret = 0
for li, ri in plus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
for li, ri in minus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
if ret == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    r = 0
    l = 0
    flg = 0
    s = S()
    for si in s:
        if si == '(':
            l += 1
        elif si == ")":
            if l > 0:
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        plus += [[l, r]]
    else:
        minus += [[l, r]]


plus.sort(key=lambda x:x[0])
minus.sort(key=lambda x:x[1], reverse=True)

ret = 0
for li, ri in plus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
for li, ri in minus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
if ret == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    r = 0
    l = 0
    flg = 0
    s = S()
    for si in s:
        if si == '(':
            flg = 1
            l += 1
        elif si == ")":
            if flg:
                flg = 0
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        plus += [[l, r]]
    else:
        minus += [[l, r]]


plus.sort(key=lambda x:x[0])
minus.sort(key=lambda x:x[1], reverse=True)

ret = 0
for li, ri in plus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
for li, ri in minus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
if ret == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
plus = []
minus = []
for _ in range(n):
    r = 0
    l = 0
    flg = 0
    s = S()
    for si in s:
        if si == '(':
            flg = 1
            l += 1
        elif si == ")":
            if flg:
                flg = 0
                l -= 1
            else:
                r += 1
    if l - r >= 0:
        plus += [[l, r]]
    else:
        minus += [[l, r]]


plus.sort(key=lambda x:x[1])
minus.sort(key=lambda x:x[1], reverse=True)

ret = 0
for li, ri in plus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
for li, ri in minus:
    ret -= ri
    if ret < 0:
        print("No")
        exit()
    ret += li
if ret == 0:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=[]
b=[]
for i in range(n):
  s=input()
  overall=0
  minimum=0
  current=0
  for j in range(len(s)):
    if s[j]=='(':
      current+=1
    else:
      current-=1
    minimum=min(current,minimum)
  overall=current
  if overall>=0:
    a.append([overall,minimum])
  else:
    b.append([overall,minimum])
finalsum=0
a=sorted(a, key=lambda t:t[1])
a.reverse()
b=sorted(b, key=lambda t:t[1])
for i in a:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
for i in b:
  if finalsum+i[1]<0:
    print('No')
    sys.exit()
  finalsum+=i[0]
if finalsum==0:
  print('Yes')
else:
  print('No')

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
T=[]
U=[]
A,B=0,0
for i in range(N):
  A,B=0,0
  for j in range(len(S[i])):
    if S[i][j]=='(':
      A+=1
    else:
      A-=1
    B=min(A,B)
  B=-B
  if A>=0:
    T.append([A,B])
  else:
    U.append([A,B])
T.sort(key=lambda x:x[1])
U.sort(key=lambda x:-x[1]*10000000+x[0])
Z=0
for i in range(len(T)):
  if Z<T[i][1]:
    print('No')
    exit()
  Z+=T[i][0]
for i in range(len(U)):
  if Z<U[i][1]:
    print('No')
    exit()
  Z+=U[i][0]
if Z:
  print('No')
else:
  print('Yes')

Submission status: Wrong Answer

Solution code:
N=int(input())
S=[input() for i in range(N)]
T=[]
U=[]
A,B=0,0
for i in range(N):
  A,B=0,0
  for j in range(len(S[i])):
    if S[i][j]=='(':
      A+=1
    else:
      A-=1
    B=min(A,B)
  B=-B
  if A>=0:
    T.append([A,B])
  else:
    U.append([A,B])
T.sort(key=lambda x:x[1])
U.sort(key=lambda x:-x[1])
Z=0
for i in range(len(T)):
  if Z<T[i][1]:
    print('No')
    exit()
  Z+=T[i][0]
for i in range(len(U)):
  if Z<U[i][1]:
    print('No')
    exit()
  Z+=U[i][0]
if Z:
  print('No')
else:
  print('Yes')

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    up, down = [], []
    for _ in range(n):
        s = list(input())
        m = 0
        height = 0
        for si in s:
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if height >= 0:
            up.append([m, height])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([j for i, j in up])-sum([j for i, j in down]) != 0:
        print("No")
        return
    h = 0
    for hi, mi in up:
        h += hi
    h = 0
    for hmi, hi in down:
        if h+hmi >= 0:
            h += hi
        else:
            print("No")
            return
    print("Yes")
    
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    up, down = [], []
    for _ in range(n):
        s = list(input())
        m = 0
        height = 0
        for si in s:
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if height >= 0:
            up.append([m, height])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([i for i, j in up])-sum([j for i, j in down]) != 0:
        print("No")
        return
    h = 0
    for hi, mi in up:
        h += hi
    h = 0
    for hmi, hi in down:
        if h+hmi >= 0:
            h += hi
        else:
            print("No")
            return
    print("Yes")
    
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    up, down = [], []
    for _ in range(n):
        s = list(input())
        m = 0
        height = 0
        for si in s:
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if height >= 0:
            up.append([height, m])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([i for i, j in up])-sum([j for i, j in down]) != 0:
        print("No")
        return
    h = 0
    for hi, mi in up:
        h += hi
    h = 0
    for hmi, hi in down:
        if h+hmi >= 0:
            h += hi
        else:
            print("No")
            return
    print("Yes")
    
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    up, down = [], []
    for _ in range(n):
        s = list(input())
        m = 0
        height = 0
        for si in s:
            if si == "(":
                height += 1
            else:
                height -= 1
                m = min(m, height)
        if m >= 0:
            up.append([height, m])
        else:
            down.append([m-height, -height])
    up.sort(reverse=True)
    down.sort(reverse=True)
    if sum([i for i, j in up])-sum([j for i, j in down]) != 0:
        print("No")
        return
    h = 0
    for hi, mi in up:
        h += hi
    h = 0
    for hmi, hi in down:
        if h+hmi >= 0:
            h += hi
        else:
            print("No")
            return
    print("Yes")
    
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append([mim, end])
  else:
    S_n.append([end-mim, end])
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().strip()

N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append([mim, end])
  else:
    S_n.append([end-mim, end])
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().strip()

N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for c in input():
    if c == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append((mim, end))
  else:
    S_n.append((end-mim, end))
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

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

N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append((mim, end))
  else:
    S_n.append((end-mim, end))
  
S_p.sort(reverse=True)
S_n.sort(reverse=True)
#print(S_p)
#print(S_n)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
S_p = []
S_n = []

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  if end >= 0:
    S_p.append((mim, end))
  else:
    S_n.append((end-mim, end))
  
S_p.sort(reverse=True)
S_n.sort()
#print(S_t)

check = 0
flag = True
for i in range(len(S_p)):
  if check + S_p[i][0] >= 0:
    check += S_p[i][1]
  else:
    flag = False
    break
  #print(check)
  
for i in range(len(S_n)):
  if check + S_n[i][1] - S_n[i][0] >= 0:
    check += S_n[i][1]
  else:
    flag = False
    break
  #print(check)
  
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
S_t = [(0,0) for _ in range(N)]

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  S_t[i] = (mim, end)
  
S_t.sort(reverse=True)
#print(S_t)

check = 0
flag = True
for i in range(N):
  if check + S_t[i][0] >= 0:
    check += S_t[i][1]
  else:
    flag = False
    break
  #print(check)
    
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
S_t = [(0,0) for _ in range(N)]

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  S_t[i] = (mim, end)
  
S_t.sort(reverse=True)
print(S_t)

check = 0
flag = True
for i in range(N):
  if check + S_t[i][0] >= 0:
    check += S_t[i][1]
  else:
    flag = False
    break
  print(check)
    
if check == 0 and flag:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
N = int(input())

S = [input() for _ in range(N)]
S_t = [(0,0) for _ in range(N)]

for i in range(N):
  end = 0
  mim = 0
  for j in range(len(S[i])):
    if S[i][j] == "(":
      end += 1
    else :
      end -= 1
    mim = min(mim,end)
  
  S_t[i] = (mim, end)
  
S_t.sort(reverse=True)

check = 0
flag = True
for i in range(N):
  if check + S_t[i][0] >= 0:
    check += S_t[i][1]
  else:
    flag = False
    break
    
if check == 0:
  flag = True
else:
  flag = False

print("Yes" if flag else "No")

Submission status: Wrong Answer

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
S.sort(key=lambda a: -a[0] - a[1])
S1 = sorted([s for s in S if s[0] + s[1] >= 0], key=lambda a: -a[1])
S2 = sorted([s for s in S if s[0] + s[1] < 0], key=lambda a: -a[0] - a[1])
cnt = 0
for s in S1:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
for s in S2:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
if cnt:
    No()
Yes()

Submission status: Wrong Answer

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
S.sort(key=lambda a: -a[0] - a[1])
S1 = sorted([s for s in S if s[0] + s[1] >= 0], key=lambda a: a[1])
S2 = sorted([s for s in S if s[0] + s[1] < 0], key=lambda a: a[1])
cnt = 0
for s in S1:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
for s in S2:
    cnt += s[1]
    if cnt < 0:
        No()
    cnt += s[0]
if cnt:
    No()
Yes()

Submission status: Wrong Answer

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
#a[0]+a[1]が大きい順に並べる
S.sort(key=lambda a: -a[0] - a[1])
#この中でa[1]が耐えられるものを貪欲にかき集める
#集められなくなったら終了


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


def f(x, y):
    return y if y[2] + cnt >= 0 else x


cnt = 0
ti = (10**10, 0, -10**10)
st = SegmentTree([(i, a[0], a[1]) for i, a in enumerate(S)], f=f, ti=ti)
for _ in range(N):
    x = st.query(0, N)
    if x[2] + cnt < 0:
        No()
    cnt += x[1] + x[2]
    st.update(x[0], ti)
if cnt == 0:
    Yes()
else:
    No()

Submission status: Wrong Answer

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


import numpy as np
N = int(input())
S = [parse(input()) for _ in range(N)]
if sum(sum(a) for a in S):
    No()
#a[0]+a[1]が大きい順に並べる
#この中でa[1]が耐えられるものを貪欲にかき集める
#集められなくなったら終了
T = np.array(sorted(S, key=lambda a: -a[0] - a[1]), dtype=int)
cnt = 0
for _ in range(N):
    K = T[T[:, 1] >= -cnt][0]
    cnt += K.sum()
    if cnt < 0:
        No()
    K = [0, -10**10]
Yes()

Submission status: Wrong Answer

Solution code:
def Yes():
    print('Yes')
    exit()


def No():
    print('No')
    exit()


def parse(s):
    ret = [0, 0]
    for c in s:
        if c == ')':
            if ret[0]:
                ret[0] -= 1
            else:
                ret[1] -= 1
        else:
            ret[0] += 1
    return ret


N = int(input())
S = [parse(input()) for _ in range(N)]
if sum(sum(a) for a in S):
    No()
S.sort(key=lambda a: -a[0] - 10**7 * a[1])
cnt = 0
for a in S:
    cnt += a[1]
    if cnt < 0:
        No()
    cnt += a[0]
Yes()

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]))
minus_que.sort(key=lambda x: (x[1]-x[2]))
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:
# 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]))
minus_que.sort(key=lambda x: (-x[0]-x[2]))
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:
# 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]))
minus_que.sort(key=lambda x: (-x[0]))
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:
# bracket sequencing

import sys


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


N = int(input())
data = []
now_value = 0
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)
    if minus >= 0:
        now_value += sums
    else:
        data.append((plus, minus, sums))

# dataの内部構造 = max+ ,min-, last_dif
data.sort(key=lambda x: (-x[2], -x[1], -x[0]))
flag = True
for x in data:
    maxi, mini, sums = x
    now_value += mini
    if now_value < 0:
        flag = False
        break
    now_value += (sums-mini)
if flag and now_value == 0:
    print("Yes")
else:
    print("No")

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 = []
now_value = 0
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)
    if minus >= 0:
        now_value += sums
    else:
        data.append(newint(minus, sums-minus))

data.sort()

flag = True

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:
#!/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 = []
now_value = 0
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)
    if minus >= 0:
        now_value += sums
    else:
        data.append(newint(minus, sums-minus))

data.sort()

flag = True

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")