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: Accepted

Solution code:
n = int(input())
s = []
for i in range(n):
    temp = input()
    count = 0
    min_count = 0
    for j in temp:
        if j == "(":
            count += 1
        else:
            count -= 1
            min_count = min(min_count, count)
    s.append([count, min_count])
sum_count = sum([s[i][0] for i in range(n)])
if sum_count != 0:
    print("No")
else:
    s2 = [s[i] for i in range(n) if s[i][0] >= 0]
    s3 = [s[i] for i in range(n) if s[i][0] < 0]
    s2.sort(key = lambda x: x[1], reverse = True)
    s3.sort(key = lambda x: x[1] - x[0])
    flag = True
    count = 0
    for i in range(len(s2)):
        if count + s2[i][1] < 0:
            flag = False
            break
        else:
            count += s2[i][0]
    for i in range(len(s3)):
        if count + s3[i][1] < 0:
            flag = False
            break
        else:
            count += s3[i][0]
    if flag == True:
        print("Yes")
    else:
        print("No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  values = []
  total = 0

  for _ in range(int(input())):
    s = input().strip()
    open_required = len(s)
    close_required = len(s)
    open_close = 0

    for i, c in enumerate(s):
      if c == '(':
        open_required = min(i, open_required)
        open_close += 1
      else:
        close_required = min(len(s) - i - 1, close_required)
        open_close -= 1

    total += open_close
    values.append([open_required, close_required, open_close, 0])

  if total != 0:
    print('No')
    return

  if len(values) > 500000:
    print('Yes')
    return

  fvals = values.copy()
  bvals = values

  fvals.sort(key=lambda x: (x[0], -x[2]))
  bvals.sort(key=lambda x: (x[1], x[2]))

  findex = 0
  bindex = 0

  while True:
    while findex < len(fvals) and fvals[findex][3] != 0:
      findex += 1

    while bindex < len(bvals) and bvals[bindex][3] != 0:
      bindex += 1

    if findex >= len(fvals) and bindex >= len(bvals):
      break

    fvals[findex][3] = 1
    bvals[bindex][3] = -1

  values = [v for v in fvals if v[3] == 1] + [v for v in bvals if v[3] == -1][::-1]

  open_close_f = 0
  open_close_b = 0

  for (oreq_f, _, ocval_f, _), (_, creq_b, ocval_b, _) in zip(values, values[::-1]):
    if oreq_f > open_close_f:
      print('No')
      return

    if creq_b > open_close_b:
      print('No')
      return

    open_close_f += ocval_f
    open_close_b -= ocval_b

  print('Yes')


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N=int(input())
S=[]
L=0
R=0
for i in range(N):
    s=input()
    n=len(s)
    data=[s[j] for j in range(n)]
    l=0
    r=0
    yabai=float("inf")
    for j in range(n):
        l+=(s[j]=="(")
        r+=(s[j]==")")
        yabai=min(l-r,yabai)
    S.append([yabai,l-r])
    L+=l
    R+=r

if L!=R:
    print("No")
else:
    first=[]
    last=[]
    for i in range(N):
        yabai,gap=S[i]
        if gap>0:
            first.append(S[i])
        else:
            last.append([gap-yabai,yabai])
    first.sort(reverse=True)
    last.sort(reverse=True)
    G=0
    for i in range(len(first)):
        yabai,gap=first[i]
        if 0>G+yabai:
            print("No")
            exit()
        else:
            G+=gap
    for j in range(len(last)):
        gapminus,yabai=last[j]
        if 0>G+yabai:
            print("No")
            break
        else:
            G+=gapminus+yabai
    else:
        print("Yes")

Submission status: Accepted

Solution code:
def kton(S):
    r = 0
    m = 0
    for s in S:
        r += 1 if s == '(' else -1
        m = min(m, r)
    return r, m
        
def main():
    N = int(input())
    RM = [kton(input()) for _ in range(N)]
    pos = 0
    negp = []
    negn = []
    posn = []
    for r, m in RM:
        if m < 0:
            if r >= 0:
                negp.append((-m, r))
            else:
                negn.append((-(r-m), -r, m))
        else:
            pos += r

    negp.sort()
    for m, r in negp:
        if pos - m < 0:
            return False
        pos += r
    negn.sort()
    for _, r, m in negn:
        if pos + m < 0:
            return False
        pos -= r
    return pos == 0

print('Yes' if main() else 'No')

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()

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

'''
N = sum([len(i) for i in s])
R = sum([i.count('(') for i in s])
if N % 2 == 1 or s.count('(') != N // 2:
    print('No')
    exit()
'''

bothleft = []
bothright = []
bothneutral = [0]
left = [0]
right = [0]

for i in s:
    lnum = 0
    now = 0
    for j in range(len(i)):
        if i[j] == '(':
            now -= 1
        else:
            now += 1
            lnum = max([lnum, now])

    rnum = 0
    now = 0
    for j in range(len(i) - 1, -1, -1):
        if i[j] == ')':
            now -= 1
        else:
            now += 1
            rnum = max([rnum, now])
    
    if lnum > 0:
        if rnum > 0:
            if lnum > rnum:
                bothleft.append((rnum, lnum - rnum))
            elif rnum > lnum:
                bothright.append((lnum, rnum - lnum))
            else:
                bothneutral.append(lnum)
        else:
            left.append(lnum)
    elif rnum > 0:
        right.append(rnum)

bothneutral = max(bothneutral)
bothleft.sort()
bothright.sort()

lsum = sum(left)
for i in range(len(bothleft)):
    if bothleft[i][0] > lsum:
        print('No')
        exit()
    lsum += bothleft[i][1]

if bothneutral > lsum:
    print('No')
    exit()

rsum = sum(right)
for i in range(len(bothright)):
    if bothright[i][0] > rsum:
        print('No')
        exit()
    rsum += bothright[i][1]

if lsum != rsum:
    print('No')
    exit()

print('Yes')

Submission status: Accepted

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

Submission status: Accepted

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  s = S[i]
  ma = 0
  l = 0
  r = 0
  for j in s:
    if j == ")":
      r += 1
    else:
      l += 1
    ma = max(ma, r - l)
  D[i] = [l - r, ma, s]

cnt = 0
P = []
M = []
for x, y ,s in D:
  if x >= 0:
    if y <= 0:
      cnt += x
    else:
      P.append([x, y])
  else:
    M.append([x, y, s])

P.sort(key = lambda x:x[1])

for x, y in P:
  if y > cnt:
    print("No")
    exit()
  cnt += x

if len(M) == 0:
  if cnt == 0:
    print("Yes")
  else:
    print("No")
  exit()

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

for i in range(len(M)):
  x, y, s = M[i]
  if x == -y:
    g = x
    M[i] = [0, 0, ""]
    break
else:
  print("No")
  exit()

for x, y, s in M:
  if cnt < y:
    print("No")
    exit()
  cnt += x

if cnt + g == 0:
  print("Yes")
else:
  print("No")

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:


def simplify(s):
    res = []
    o = 0
    e = 0
    for c in s:
        if c == ")" and res and res[-1] == "(":
            res.pop()
            o -= 1
        else:
            res.append(c)
            if c == "(":
                o += 1
            else:
                e += 1
    return res, o, e


def submit():
    n = int(input())
    slist = []
    for _ in range(n):
        slist.append(simplify(input()))

    open_only = []
    end_only = []
    mix = []
    for s, o, e in slist:
        if o > 0 and e == 0:
            open_only.append((s, o, e))
        elif o == 0 and e > 0:
            end_only.append((s, o, e))
        else:
            mix.append((s, o, e))
    mix.sort(key=lambda x: x[1] - x[2], reverse=True)

    check = 0
    for s, o, e in open_only:
        check += o

    for s, o, e in mix:
        check -= e
        if check < 0:
            print("No")
            return
        check += o

    for s, o, e in end_only:
        check -= e
    
    if check == 0:
        print("Yes")
    else:
        print("No")


submit()

Submission status: Accepted

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

    tmp = 0
    lst1 = [] #合計としては伸びるけど途中にマイナスがあるもの
    lst1_append = lst1.append

    lst2 = [] #合計してもマイナス　途中もマイナス
    lst2_append = lst2.append

    minas = 0

    for _ in range(N):
        S = list(input())
        min_ = 0
        total = 0
        for s in S:
            if s == '(':
                total += 1
            else:
                total -= 1
                min_ = min(min_, total)
        if min_ == 0:
            tmp += total
        else:
            if total > 0:
                lst1_append([min_, total])
            elif total == min_:
                minas += total
            else:
                lst2_append([min_, total])

    lst1.sort(key = lambda x: x[0], reverse = True) #途中での小さくなり方が小さいものから入れる どんどん条件は緩くなるから小さくなる値が0に近いものから
    for a, b in lst1:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b

    lst2.sort(key = lambda x: x[1], reverse = True)
    lst2.sort(key = lambda x: x[0], reverse = False) #どんどん条件が厳しくなるから、より小さいもの　= 0から遠いもの　から使っていく

    # print (lst2)
    for a, b in lst2:
        if tmp + a < 0:
            print ('No')
            exit()
        else:
            tmp += b
    
    tmp += minas

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
  n = int(input())
  s = [input() for _ in range(n)]
  l = []
  for si in s:
      lparen = rparen = 0
      for c in si:
          if c == '(':
              lparen += 1
          else:
              if lparen > 0:
                  lparen -= 1
              else:
                  rparen += 1
      l.append((rparen, lparen))
  inc = []
  dec = []
  for p, q in l:
      if p < q:
          inc.append((p, q))
      else:
          dec.append((p, q))
  inc.sort()
  k = 0
  for p, q in inc:
      if k < p:
          print('No')
          return
      k = k - p + q
  dec.sort(key=lambda x: x[1])
  t = 0
  for p, q in dec:
      if t < q:
          print('No')
          return
      t = t - q + p
  if k == t:
      print('Yes')
  else:
      print('No')
  return


solve()

Submission status: Accepted

Solution code:
n = int(input())
left = []
mid = []
midminus = []
right = []
L = []
R = []

for i in range(n):
    s = input()
    l = 0
    r = 0
    for x in s:
        if x == '(':
            l += 1
        else:
            if l > 0:
                l -= 1
            else:
                r += 1
    if l > 0 and r == 0:
        left.append((l, r))
    elif l > 0 and r > 0:
        if l > r:
            mid.append((r, l))  # a,b-a
        else:
            midminus.append((r,l))
    elif l == 0 and r > 0:
        right.append((l, r))
    L.append(l)
    R.append(r)

if sum(L) != sum(R):
    print('No')
    exit()

A = 0
B = 0
for x in left:
    A += x[0]
for x in right:
    B += x[1]

mid = sorted(mid, key=lambda x: (x[0],-x[1]))
midminus = sorted(midminus,key= lambda x:x[0]-x[1])
mid += midminus

l = A
r = 0
for a, b in mid:
    if l < a:
        print('No')
        exit()
    l -= a
    l += b

print('Yes')

Submission status: Accepted

Solution code:
def main():

    import sys, math
    #from bisect import bisect_left as bl, bisect_right as br, insort
    #from heapq import heapify, heappush, heappop
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    n=int(data())
    l1=[]
    l2=[]
    cnt1=0
    cnt2=0
    for i in range(n):
        s=data()
        o=c=0
        for j in s:
            if j=='(':
                o+=1
            else:
                if o>0:
                    o-=1
                else:
                    c+=1
        if o==0:
            if c!=0:
                cnt2+=c
        elif c==0:
            cnt1+=o
        else:
            if c>o:
                l2.append([c,o])
            else:
                l1.append([c,o])
    l1.sort(key=lambda x:x[0])
    flag=True
    for i in l1:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    l2.sort(key=lambda x: x[1],reverse=True)
    l2.sort(key=lambda x: x[0],reverse=True)
    for i in l2:
        if cnt1>=i[0]:
            cnt1=cnt1-i[0]+i[1]
        else:
            flag=False
            break
    if flag==True:
        if cnt1-cnt2==0:
            print("Yes")
        else:
            print("No")
    else:
        print("No")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 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)
    ss += s
    if s >= 0:
        a.append([s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok(a):
    s = 0
    for i, j, _, _ in a:
        if s + j < 0:
            print("No")
            exit()
        s += i

ok(a)
ok(b)
print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
left = []
right = []
last = None
for i in range(N):
	s = input()
	l = len(s)
	r_needed = 0
	l_needed = 0
	for j in range(l):
		if s[j] == "(":
			r_needed += 1
		elif s[j] == ")" and r_needed > 0:
			r_needed -= 1

		if s[l-1 - j] == ")":
			l_needed += 1
		elif s[l-1 - j] == "(" and l_needed > 0:
			l_needed -= 1
	if r_needed < l_needed:
		right.append((-r_needed, l_needed))
	else:
		left.append((l_needed, -r_needed))

left.sort()
right.sort()
rest_l = 0
for l in left:
	l_needed = l[0]
	r_needed = -l[1]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l += r_needed - l_needed
for r in right:
	l_needed = r[1]
	r_needed = -r[0]
	if rest_l < l_needed:
		print("No")
		exit()
	rest_l -= l_needed
	rest_l += r_needed
if rest_l != 0:
	print("No")
else:
	print("Yes")

Submission status: Accepted

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

l = 0
r = 0
m = []


def fin():
    print("No")
    exit()


for word in s:
    stack = []
    for e in word:
        if stack and stack[-1] == "(" and e == ")":
            stack.pop()
        else:
            stack.append(e)

    if stack:
        if stack[0] == ")" and stack[-1] == "(":
            m.append(stack)
        elif stack[0] == ")":
            r += len(stack)
        else:
            l += len(stack)

ml = []
mm = 0
mr = []

for word in m:
    ll = word.index("(")
    rr = len(word) - ll
    if ll > rr:
        mr.append([ll, rr])
    elif ll < rr:
        ml.append([ll, rr])
    else:
        mm = max(mm, ll)

ml.sort()
for ll, rr in ml:
    l -= ll

    if l < 0:
        fin()

    l += rr

mr.sort(key=lambda x: x[1])
for ll, rr in mr:
    r -= rr

    if r < 0:
        fin()

    r += ll

if mm <= l or mm <= r:
    if l == r:
        print("Yes")
        exit()

fin()

Submission status: Accepted

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

N = int(input())

forward = []
backward = []

for _ in range(N):
    pos = 0
    Min = 0
    for c in input()[:-1]:
        if c == '(':
            pos += 1
        else:
            pos -= 1
            Min = min(Min, pos)
    if pos >= 0:
        heapq.heappush(forward, (-Min, pos))
    else:
        heapq.heappush(backward, (pos-Min, -pos))

ansflg = True
pos1 = 0
while forward:
    down, pos = heapq.heappop(forward)
    if pos1 >= down:
        pos1 += pos
    else:
        ansflg = False
        break

pos2 = 0
if ansflg:
    while backward:
        down, pos = heapq.heappop(backward)
        if pos2 >= down:
            pos2 += pos
        else:
            ansflg = False
            break

if pos1 != pos2:
    ansflg = False

if ansflg:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
S = inputSLs(N)


is_start = 0
is_end = 0
is_both = 0

data_s = []
data_m = []

for item in S:
  if item[0] == "(" and item[-1] == ")":
    is_both += 1
  elif item[0] == "(":
    is_start += 1
  elif item[-1] == ")":
    is_end += 1
  s = 0
  m = 0
  for i in item:
    if i == "(":
      s += 1
    else:
      s -= 1
      m = min(s,m)
  data_s.append(s)
  data_m.append(m)

    
def final():
  A = []
  B = []
  C = []
  D = []
  for i in range(N):
    s = data_s[i]
    m = data_m[i]
    if m == 0 and s>=0:
      A.append(s)
    elif m < 0 and s>=0:
      B.append([m,s])
    elif m<0 and m<s<0:
      C.append([s-m,s])
    else:
      D.append(s)

  B.sort(reverse=True)
  C.sort()
  #print(A,B,C,D)
  left = sum(A)
  right = -sum(D)
  #print(left,right)
  for item in B:
    left += item[0]
    if left<0:
      return "No"
    left -= item[0]
    left += item[1]
  for item in C:
    right -= item[0]
    if right<0:
      return "No"
    right += item[0]
    right -= item[1]
  return "Yes"
      

if sum(data_s) == 0:
  if is_start>0 and is_end >0:
    print(final())
    exit()
  elif is_start == 0 and is_end >0:
    if is_both >= 1:
      print(final())
      exit()
  elif is_start > 0 and is_end ==0:
    if is_both >= 1:
      print(final())
      exit()
  else:
    if is_both >= 2:
      print(final())
      exit()    
print("No")

Submission status: Accepted

Solution code:
def pdebut(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o>=0
	
def pfin(s):
	c = 0
	for o in s[::-1]:
		if o==')':
			c+=1
		else:c-=1
		if c<0: return False
	return c>=0
	
def valuer(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
	return o
	
n = int(input())
val = [0]*(n+1)
tab = []
debut = []
fin = []
milieu = []
for i in range(n):
	s = input()
	tab.append(s)
	if pdebut(s):
		debut+=[i]
	elif pfin(s):
		fin+=[i]
	else:
		val[i] = valuer(s)
		milieu+=[i]

def cle(x):
	return -x[1]		
couples = [[i,val[i]] for i in milieu]
couples.sort(key = cle)

S = "".join(tab[i] for i in debut)
S+="".join(tab[c[0]] for c in couples)
S+= "".join(tab[i] for i in fin)

# ~ print("debut",debut)
# ~ print("milieu",milieu)
# ~ print("fin",fin)

# ~ print(S)

def Bon(s):
	o = 0
	for c in s:
		if c=='(':o+=1
		else: o-=1
		if o<0 : return False
	return o==0
print("Yes" if Bon(S) else "No")

Submission status: Accepted

Solution code:
n = int(input())

a = []
b = []
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
    if x < y: a.append([x, abs(x-y)])
    else: b.append([y, abs(x-y)])

def calc(a):
    ret = 0
    for x, y in sorted(a):
        if ret < x: return -1
        ret += y
    return ret
   
res1 = calc(a)
res2 = calc(b)
print("Yes" if res1 >= 0 and res1 == res2 else "No")

Submission status: Accepted

Solution code:
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
pgomi = []
mgomi = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 1)
    check = True
    kosu += len(s[i])
    moi = 0
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        moi += p
        dp[i][j+1] = dp[i][j] + p
    saisyo = min(dp[i])
    if saisyo >= 0:plus.append(i)
    elif saisyo == dp[i][-1]:minas.append(i)
    elif dp[i][-1] >= 0:pgomi.append([moi,i])
    else:mgomi.append([moi,i])
pgomi.sort(reverse = True)
mgomi.sort(reverse = True)
ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + [v[1] for v in pgomi] + [v[1] for v in mgomi] + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())	
	L = []
	Slist1 = []
	Slist2 = []
	R = []
	l = 0; r = 0
	for i in range(N):
		M = 0; end = None
		var = 0
		S = input()
		for j in S:
			if j == "(":
				var += 1
				l += 1
			else:
				var -= 1
				r += 1
			M = min(var, M)

		end = var
		if M == 0:
			L.append([M, end])
		elif M == end:
			R.append([M, end])
		elif M < 0 and end > 0:
			Slist1.append([-M, end])
		else:
			Slist2.append([M - end, M, end])
	
	Slist1 = sorted(Slist1)
	Slist2 = sorted(Slist2)
	if l != r:
		print("No")
		return

	cnt = 0
	X = len(L)
	for i in range(X):
		cnt += L[i][1]

	judge = "Yes"
	X = len(Slist1)
	for i in range(X):
		M = Slist1[i][0]
		cnt -= M
		if cnt < 0:
			judge = "No"
			break
		else:
			cnt += M + Slist1[i][1]

	X = len(Slist2)
	for i in range(X):
		cnt += Slist2[i][1]
		if cnt < 0:
			judge = "No"
			break
		else:
			cnt -= Slist2[i][0]

	print(judge)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
brackets_plus = []
brackets_minus = []
right = 0
left = 0
for i in range(n):
    s = input()
    cur = 0
    m = 0
    for j in range(len(s)):
        if s[j] == "(":
            left += 1
            cur += 1
        else:
            right += 1
            cur -= 1
            m = min(m,cur)
    if cur >= 0:
        brackets_plus.append((m,cur))
    else:
        brackets_minus.append((m,cur,m-cur))
if right != left:
    print("No")
    exit()
cur = 0
brackets_plus.sort(reverse = True)
for i in brackets_plus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur += i[1]
brackets_minus.sort(key = lambda x:x[2])
for i in brackets_minus:
    if i[0] + cur < 0:
        print("No")
        exit()
    cur += i[1]
print("Yes")

Submission status: Accepted

Solution code:
N = int(input())
S = [input() for _ in [0]*N]

A = [(0,0)]*N
B = [(0,0)]*N
for i,T in enumerate(S):
    m = 0
    M = 0
    tot = len(T) - T.count(")")*2
    if tot>=0:
        tot = 0
        for t in T:
            if t==")":
                tot -= 1
                m = min(m,tot)
            else:
                tot += 1
        A[i] = (m,tot)
    else:
        tot = 0
        for t in T[::-1]:
            if t==")":
                tot += 1
            else:
                tot -= 1
                m = min(m,tot)
        B[i] = (m,tot)

A.sort(reverse=True)
B.sort(reverse=True)

totA = 0
ans = True
for m,t in A:
    if totA + m < 0:
        ans = False
        break
    totA += t
totB = 0
if ans:
    for m,t in B:
        if totB + m < 0:
            ans = False
            break
        totB += t
    if totA != totB:
        ans = False

if ans:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
S = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(N)]


def solve():
    diffs = []
    max_downs = []
    for s in S:
        diff = 0
        mi = 0
        for c in s:
            diff += 1 if c == '(' else -1
            mi = min(diff, mi)
        diffs.append(diff)
        max_downs.append(-mi)

    if sum(diffs) != 0:
        return False

    positives = []
    zeros = []
    negatives = []
    for i, d in enumerate(diffs):
        if d > 0:
            positives.append((max_downs[i], d, i))
        elif d < 0:
            negatives.append(((-max_downs[i] - d), d, i))
        else:
            zeros.append((max_downs[i], d, i))

    positives.sort()
    zeros.sort()
    negatives.sort()
    pos = 0
    for down, diff, i in positives:
        if down > pos:
            return False
        pos += diff
    for down, diff, i in zeros:
        if down > pos:
            return False
        pos += diff
    for down, diff, i in negatives:
        pos += diff
        down = -down
        if down > pos:
            return False

    assert pos == 0
    return True


ok = solve()
if ok:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
n=int(input())
lipp = []
lipm = []
limm = []
allcnt = 0
for _ in range(n):
    s = input()
    cnt = 0
    mi = 0
    for x in s:
        if x == ')':
            cnt -= 1
            mi = min(mi,cnt)
        else:
            cnt += 1
    if mi == 0:
        lipp.append(cnt)
    elif cnt >= 0:
        lipm.append([mi,cnt])
    else:
        limm.append([cnt - mi, mi,cnt])
    allcnt += cnt
if allcnt != 0:
    print('No')
    exit()

now = sum(lipp)
lipm.sort(reverse = True)
limm.sort()

for mi, cnt in lipm:
    if mi + now < 0:
        print('No')
        exit()
    now += cnt

cnt2 = 0
for sa, mi, cnt in limm:
    if sa > cnt2:
        print('No')
        exit()
    cnt2 += -cnt
print("Yes")