TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
N,M,K = map(int,input().split())
# dp = [[0]*(K+2) for _ in range(2)]

# print (1)
# dp[0][0] = M
# MOD = 998244353
# for n in range(N-1):
#     n = n % 2
#     a = (n+1) % 2

#     for k in range(K+1):
        
        
        
#         dp[a][k] += dp[n][k] * (M-1)
#         dp[a][k+1] += dp[n][k]
#         dp[a][k] %= MOD
#         dp[a][k+1] %= MOD
# #print (dp)
# print(sum(dp[(N+1)%2][:-1]))
import numpy as np
old = np.zeros(K+1).astype(np.int)
MOD = 998244353
old[0] = M
for n in range(N-1):
    new = old*(M-1)
    new[1:] += old[:K]
    new %= MOD
    old = new
print (sum(new)%MOD)

N,M,K = map(int,input().split())
MOD = 998244353
ans = 0


fact = [1] * (N+1) 
factinv = [1] * (N+1) 



for i in range(N):
    fact[i+1] = fact[i] * (i+1) % MOD 
    factinv[i+1] = pow(fact[i+1], MOD-2, MOD)

def nCk(n,k): 
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD) * nCk(N-1,k)
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

Verdicts: Runtime Error

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
n, m, k = map(int, input().split())
if n <= k+1:
    print(m**n)
else:
    a = [m*((m-1)**(n-1))]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]/(i+1)*(n-i-1)))
    for i in range(k):
        a.append(int((a[-1]*b[i+1])/b[i]/(m-1))
    for i in range(k+1):
        c += a[i]
    print(c%998244353)

n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    d = m
    for i in range(n-1):
        d = d*(m-1)%z
    a = [d]
    b = [1]
    c = 0
    for i in range(k):
        b.append(int(b[-1]*(n-i-2)/(i+1)%z))
    for i in range(k):
        a.append(int((a[-1]*b[i+1]%z)/b[i]/(m-1)))
    for i in range(k+1):
        c = (c+a[i])%z
    print(c)

n, m, k = map(int, input().split())
z = 998244353
if n <= k+1:
    a = 1
    for i in range(n):
        a = a*m%z
    print(a)
else:
    a = []
    b = []
    d = [1, 1]
    e = [1, 1]
    f = [0, 1]
    for i in range(2, n):
        d.append(d[-1]*i%z)
        f.append((-f[z%i]*(z//i))%z)
        e.append(e[-1]*f[-1]%z)
    for i in range(k+1):
        b.append(d[n-1]*e[i]*e[n-i-1]%z)
    x = 0
    g = [1]
    for i in range(n-1):
        g.append(g[i]*(m-1)%z)
    for i in range(k+1):
        a.append(b[i]*m*g[n-i-1]%z)
    for i in range(k+1):
        x = (x+a[i])%z
    print(x)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
M = 998244353
n,m,K = map(int,input().split())
ans = 0
c = 1
for k in range(K+1):
    ans += c * m * pow(m-1,n-k-1,M)
    c *= (n-k+1) * pow(k+1,M-2,M)
    ans %= M
    c %= M
print(ans)
    


M = 998244353
n,m,K = map(int,input().split())
ans = 0
c = 1
for k in range(K+1):
    ans += c * m * pow(m-1,n-k-1,M)
    c *= (n-k-1) * pow(k+1,M-2,M)
    ans %= M
    c %= M
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
n, m, k = map(int, input().split())

MOD = 998244353

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

ans = 0
for i in range(k + 1):
  ans += ((m ** (i + 1)) * (m - 1) ** (n - 1 - i) * comb(n-1, i, MOD)) % MOD
print(ans % MOD)

n, m, k = map(int, input().split())

MOD = 998244353

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

def pow_k(x, n, mod):
    
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x

ans = 0
for i in range(k + 1):
  ans += (pow_k(m, i + 1, MOD) * pow_k(m - 1, n - 1 - i, MOD) * comb(n - 1, i, MOD)) % MOD
print(ans % MOD)

n, m, k = map(int, input().split())

MOD = 998244353

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % MOD

inv[n] = pow(fac[n], MOD-2, MOD)
for j in range(n - 1, -1, -1):
    inv[j] = inv[j + 1] * (j + 1) % MOD

def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % MOD

ans = 0
for i in range(k + 1):
  ans += (m * pow(m - 1, n - i - 1, MOD) * comb(n - 1, i)) % MOD
print(ans % MOD)


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m,k=map(int,input().split())
    mod=998244353
    ans=0
    for kx in range(k+1):
        ans+=m*(m-1)**(n-1-kx)%mod
    print(ans%mod)


if __name__=='__main__':
    main()

import sys
def input(): return sys.stdin.readline().rstrip()
class mod_comb3:
    def __init__(self,mod=10**9+7,n_max=1):
        self.mod,self.n_max=mod,n_max
        self.fact,self.inv,self.factinv=[1,1],[0,1],[1,1]
        if 1<n_max:setup_table(n_max)
    def comb(self,n,r):
        if r<0 or n<r:return 0
        if self.n_max<n:self.setup_table(n)
        return self.fact[n]*(self.factinv[r]*self.factinv[n-r]%self.mod)%self.mod
    def setup_table(self,t):
        for i in range(self.n_max+1,t+1):
            self.fact.append(self.fact[-1]*i%self.mod)
            self.inv.append(-self.inv[self.mod%i]*(self.mod//i)%self.mod)
            self.factinv.append(self.factinv[-1]*self.inv[-1]%self.mod)
        self.n_max=t

def main():
    n,m,k=map(int,input().split())
    mod=998244353
    f=mod_comb3(mod)
    ans=0
    t=m*pow(m-1,n-1-k,mod)
    for kx in range(k,-1,-1):
        ans+=f.comb(n-1,kx)*t%mod
        t=t*(m-1)%mod
    print(ans%mod)

if __name__=='__main__':
    main()

Verdicts: Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
import sys

n,m,k=map(int,input().split())
MOD=998244353

if n>m+k:
  print(0)
  sys.exit()


def COMinit():
  fac[0] = 1
  fac[1] = 1
  finv[0] = 1
  finv[1] = 1
  inv[1] = 1
  for i in range(2,MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def COM(n, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
  
  
MAX=10000000
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

def HCOM(n,r):
  return COM(n+r-1,r)
  
#t=max(1,n-k)!
t=m
if n-k>1:
  for i in range(2,max(2,n-k)):
    t*=m-1
    t%=MOD
#print(t)

ans=0
for c in range(max(1,n-k),n+1):
  if c>1:
    t*=m-1
  t%=MOD
  #print("c=",c,"t=",t,"HCOM=",HCOM(c,n-c))
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

import sys

n,m,k=map(int,input().split())
MOD=998244353


def COMinit():
  fac[0] = 1
  fac[1] = 1
  finv[0] = 1
  finv[1] = 1
  inv[1] = 1
  for i in range(2,MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def COM(n, k):
  if n < k:
    return 0
  if n < 0 or k < 0:
    return 0
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
  
  
MAX=n+1
fac=[0]*MAX
finv=[0]*MAX
inv=[0]*MAX

COMinit()

def HCOM(n,r):
  return COM(n+r-1,r)
  
#t=max(1,n-k)!
t=m
if n-k>1:
  for i in range(1,n-k-1):
    t*=m-1
    t%=MOD
#print(t)

ans=0
for c in range(n-k,n+1):
  if c>1:
    t*=m-1
  t%=MOD
  #print("c=",c,"t=",t,"HCOM=",HCOM(c,n-c))
  ans+=t*HCOM(c,n-c)
  ans%=MOD
  
  
  
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)
ue=fact[n-1]
iii=m*pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
print(ans%mod)


n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=comb(n-1,i)po%mod
    po*=iii
    po%=mod
print(ans%mod)

n,m,k=map(int,input().split())
mod1,mod2=10**9+7,998244353
mod=mod2
MAX=n-1
fact=[1]*(MAX+1)
inv=[1]*(MAX+1)
for i in range(2,MAX+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
ans=0
cor=pow(m-1,n-1-k,mod)
for i in range(k,-1,-1):
    ans=(ans+comb(n-1,i)*cor)%mod
    cor=cor*(m-1)%mod

print(m*ans%mod)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

ans=0
a=1
for i in range(k+1):
    ans+=a*m*(((m-1)**(n-1-k)))
    a=a*(n-1-i+1)//(i+1)
print(ans%998244353)

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

ans=0
for i in range(k+1):
    a=1
    ans+=a*m*(((m-1)**(n-1-k)))
    a=a*(n-1-i+1)//(i+1)
print(ans%998244353)

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

def cmb(n, k, mod, fac, ifac):
    
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

ans=0
a=1
MOD=998244353
fac, ifac = make_tables(MOD, n-1)
        
for i in range(k+1):
    ans+=m*pow(m-1,n-1-i,998244353)*cmb(n-1, i, MOD, fac, ifac)
print(ans%998244353)

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
n,m,k = map(int,input().split())
mod = 998244353
dp = [[0] * (n+1) for i in range(n+1)]
dp[1][0] = m
for i in range(2, n+1):
    dp[i][0] = (dp[i-1][0] * (m-1)) % mod
for i in range(2, n+1):
    dp[i][1] = (dp[i-1][0] + dp[i-1][1] * (m-1)) % mod

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m


minv = modinv(m, mod)
i = 2
while i <= n:
    j = 2
    while j <= k:
        dp[i][j] = (dp[i//2][j//2] ** 2 * minv * (m-1)) % mod
        j *= 2
    i *= 2

ans = 0
for i in range(k+1):
    for j in range(50):
        if n >> j & 1:
            dp[n][i] += dp[j][i]
print(sum(dp[n][:k+1]))


n,m,k = map(int,input().split())
mod = 998244353
ans = 0
fact = [1,1]
finv = [1,1]
for i in range(2, n+1):
    fact += [fact[i-1] * i % mod]
    finv += [pow(fact[i], mod-2, mod)]


def comb(n,k, mod):
    return (fact[n] * finv[k] * finv[n-k]) % mod



for i in range(0, k+1):
    ans += m * pow(m-1, n-i-1, mod) * comb(n-1, i, mod)
    ans %= mod
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
 = 998244353
n, m, k = map(int, input().split())
 
fact = [0]*(n+1)
fact[0] = 1
for i in range(1, n+1):
    fact[i] = fact[i-1]*i % MOD
 
invfact= [0]*(n+1)
for i in range(n+1):
    invfact[i] = pow(fact[i], MOD-2, MOD)
 
 
def nCk(n, k):
    return fact[n]*invfact[k]*invfact[n-k]
 
 
ans = 0
for i in range(k+1):
    ans += m*pow(m-1, n-1-i, MOD)*nCk(n-1, i)
    ans %= MOD
print(ans)

import sys
 
input = sys.stdin.readline
 
def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod
 
mod = 998244353
N, M, K = map(int, input().split())
 
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod 
# print('fact:{}'.format(fact))
revfact = [1] * (N + 1) 
revfact[N] = pow(fact[N], mod - 2, mod) 
# print('revfact:{}'.format(revfact))
for i in reversed(range(1, N)): 
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
# print('revfact:{}'.format(revfact))
 
ans = 0
for k in range(K + 1):
    ans += (M * pow(M - 1, N - 1 - k, mod) * comb(N - 1, k)) % mod
    ans %= mod
print(ans)

Verdicts: Runtime Error

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def solve():
    N, M, K = map(int, input().split())
    mod = 998244353

    nCi = [1]
    for i in range(1, N):
        nCi.append(nCi[i - 1] * (N - i) * inverse(i, mod) % mod)
        
    print(nCi)
    ans = 0
    for k in range(K + 1):
        n = N - k
        ans += M * int(pow((M - 1), n - 1, mod)) * nCi[k]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()


def inverse(a, p):
    a_, p_ = a, p
    x, y = 1, 0
    while p_:
        t = a_ // p_
        a_ -= t * p_
        a_, p_ = p_, a_
        x -= t * y
        x, y = y, x
    x %= p
    return x


def solve():
    N, M, K = map(int, input().split())
    mod = 998244353

    nCi = [1]
    for i in range(1, N):
        nCi.append(nCi[i - 1] * (N - i) * inverse(i, mod) % mod)
    ans = 0
    for k in range(K + 1):
        n = N - k
        ans += M * int(pow((M - 1), n - 1, mod)) * nCi[k]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()


Verdicts: Wrong Answer

Accepted
Problem: There are N blocks arranged in a row. Let us paint these blocks.  We will consider two ways to paint the blocks different if and only if there is a block painted in different colors in those two ways.  Find the number of ways to paint the blocks under the following conditions:    * For each block, use one of the M colors, Color 1 through Color M, to paint it. It is not mandatory to use all the colors.   * There may be at most K pairs of adjacent blocks that are painted in the same color.  Since the count may be enormous, print it modulo 998244353.

Submission attempts (in order):
n,m,k=map(int,input().split())
mod=998244353
cntb=1
for i in range(k+1):
    # cntb*=(n-i)//i
    ans+=((m*pow(m-1,n-1-i,mod)％mod)*cntb)%mod
    ans%=mod
    cntb*=((n-i−1)*pow(i+1,mod-2,mod))%mod
print(ans%mod)

n,m,k=map(int,input().split())
mod=998244353
cntb=1
ans=0
for i in range(k+1):
    ans=ans+(((m*pow(m-1,n-1-i,mod))%mod)*cntb)%mod
    ans=ans%mod
    cntb=(cntb*(n-1-i)*pow(i+1,mod-2,mod))%mod
print(ans%mod)

Verdicts: Runtime Error

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = len(min_s)-b_count
    bi = b_count
    if bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

sorted(first_list, key=lambda s: s[1])
sorted(last_list, key=lambda s: s[1], reverse=True)

ans = ""
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]

a_count = 0
b_count = 0
min_s = ""
for c in s:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

n = int(input())
slist = []
for i in range(n):
    slist.append(input())

first_list = []
last_list = []
first = ""
last = ""
for i in range(n):
    s = slist[i]

    a_count = 0
    b_count = 0
    min_s = ""
    for c in s:
        if c == ")":
            b_count-=1
        else:
            b_count+=1
        if b_count < 0:
            b_count = 0
            a_count+= 1
    min_s = ")"* a_count + "("*b_count

    ai = a_count
    bi = b_count

    if ai == 0:
        first += min_s
    elif bi == 0:
        last += min_s
    elif bi-ai >= 0:
        first_list.append([min_s,ai])
    else:
        last_list.append([min_s,bi])

first_list= sorted(first_list, key=lambda s: s[1])
last_list= sorted(last_list, key=lambda s: s[1], reverse=True)

ans = first
for i in range(len(first_list)):
    ans += first_list[i][0]
for i in range(len(last_list)):
    ans += last_list[i][0]
ans += last

a_count = 0
b_count = 0
min_s = ""
for c in ans:
    if c == ")":
        b_count-=1
    else:
        b_count+=1
    if b_count < 0:
        b_count = 0
        a_count+= 1

if a_count == 0 and b_count == 0:
    print("Yes")
else:
    print("No")

Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache






A=list(map(int,input().split()))
n=len(A)
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in A[i]:
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum([PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")


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


n=int(input())
A=[]
#
PM=[[0,0] for i in range(n)]
for i in range(n):
    now=0
    mini=0
    for j in input():
        if j=="(": now+=1 
        else:
            now-=1 ; mini=min(mini,now)
    PM[i]=[mini,now]

if sum( [PM[i][1] for i in range(n)]  )!=0 : 
    print("No")
    exit()

MINI=0
NOW=0
PMf=[PM[i] for i in range(n) if PM[i][1]>=0]
PMf.sort()
for i in range(len(PMf)):
    MINI=min(MINI , NOW+PMf[-i-1][0] )
    NOW+=PMf[-i-1][1]
    if MINI<0 : print("No") ; exit()

PMs=[PM[i] for i in range(n) if PM[i][1]<0]
PMs=sorted(PMs , key=lambda x : x[1]-x[0])
for i in range(len(PMs)):
    MINI=min(MINI , NOW+PMs[-i-1][0] )
    NOW+=PMs[-i-1][1]
    if MINI<0 : print("No") ; exit()

print("Yes")


Verdicts: Runtime Error

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(input())

ls = []
rs = []

total = 0
for i in range(n):
    s = input().strip()

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
            total += 1
        else:
            h -= 1
            b = min(b, h)
            total -= 1

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))

if total != 0:
    print("NO")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

b = 0
total = 0
OK = True
for p in ls:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

for p in rs:
    b += p[0]
    total += p[1]
    if b < 0:
        OK = False

if not OK:
    print("NO")
else:
    print("YES")




import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# n = map(int, readline().split())
n = int(readline())

ls = []
rs = []

total = 0
S = list(map(lambda x: x.strip().decode(), readlines()))

for i in range(n):
    s = S[i]

    b = 0
    h = 0
    for c in s:
        if c == '(':
            h += 1
        else:
            h -= 1
            b = min(b, h)

    if h >= 0:
        ls.append((b, h))
    else:
        rs.append((b - h, -h))
    total += h

if total != 0:
    print("No")
    exit()

ls = sorted(ls, reverse=True)
rs = sorted(rs, reverse=True)

h = 0
OK = True
for p in ls:
    b = h + p[0]
    h += p[1]
    if b < 0:
        OK = False

h = 0
for p in rs:
    b = h + p[0]
    h += p[1]
    if b < 0 or h < 0:
        OK = False

if not OK:
    print("No")
else:
    print("Yes")




Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
import sys
def main():
    N = int(input())
    S = [sys.stdin.readline().strip() for i in range(N)]
    DR = []
    for s in S:
        d = 0    
        rmax = 0 
        # rmax <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                rmax = min(d, rmax)

        DR.append((d, rmax))

    # print(DR)
    
    
    
    

    
    DR.sort(key=lambda x: (-x[1], x[0]))
    # print(DR)
    D = 0
    ans = 'yes'
    for dr in DR:
        d, r = dr
        if D + r < 0:
            ans = 'No'
            break
        D += d
    
    if D != 0:
        ans = 'No'
    print(ans)

if __name__ == '__main__':
    main()

def check(DR):
    D = 0
    for dr in DR[::-1]:
        dmin, d = dr
        if D + dmin < 0:
            return False
        D += d
    return True

def main():
    N = int(input())
    S = []
    for i in range(N):
        S.append(input())

    DR1 = []
    DR2 = []
    total = 0
    for s in S:
        d = 0    
        d_min = 0 
        # d_min <= d
        for lr in s:
            if lr == '(':
                d += 1
            else:
                d -= 1
                d_min = min(d, d_min)
        total += d
        if d > 0:
            DR1.append((d_min, d))
        else:
            DR2.append((d_min - d, -d))

    
    DR1.sort()
    DR2.sort()
    if check(DR1) and check(DR2) and sum([d[1] for d in DR1]) == sum([d[1] for d in DR2]):
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
n = int(input())
sco = [] 
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    sco.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

sco.sort(reverse = True)
for i in range(n):
    now = 0
    if sco[i][0] + now < 0:
        print("No")
        exit()
    else:
        now += sco[i][1]

print("Yes")


n = int(input())
scop = [] 
scom = []
ssum = 0

for i in range(n):
    s = input()
    sa = 0
    ms = 0
    for i in range(len(s)):
        if s[i] == "(":
            sa += 1
        else:
            sa -= 1
        if ms > sa:
            ms = sa
    if sa > 0:
        scop.append([ms,sa])
    elif not sa == ms:
        scom.append([ms,sa])
    ssum += sa

if not ssum == 0:
    print("No")
    exit()

scop.sort(reverse = True)
scom.sort()

now = 0
for i in scop:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]
for i in scom:
    if now + i[0] < 0:
        print("No")
        exit()
    now += i[1]

print("Yes")


Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
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]


	# ~ return -x[1]		

# ~ 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("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")


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


Verdicts: Runtime Error

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
N = int(input())
S_list = [input() for _ in range(N)]

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack and stack[-1] == ')':
                stack.append('(')
                l = 1
            else:
                stack.append('(')
                l += 1
        else:   # s==')'
            if stack and stack[-1] == '(':
                stack.pop()
                l -= 1
            else:
                stack.append(')')
                r += 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, rev_r)
        min_revl = min(min_revl, rev_l)
    # print('{} l:{} r:{} left:{} rev_l:{} rev_r:{} right:{}'.format(
        

if left+rev_l == rev_r+right and left >= min_revr and min_revl <= right:
    print('Yes')
else:
    print('No')


N = int(input())
S_list = [input() for _ in range(N)]

min_revr, min_revl = 10**20, 10**20
left, rev_l, rev_r, right = 0, 0, 0, 0
for S in S_list:
    stack = []
    l, r = 0, 0
    for s in S:
        if s == '(':
            if stack:
                if stack[-1] == ')':
                    stack.append('(')
                    l = 1
                else:
                    stack.append('(')
                    l += 1
            else:
                stack.append('(')
                l = 1
        else:   # s==')'
            if stack:
                if stack[-1] == '(':
                    stack.pop()
                    l -= 1
                else:
                    stack.append(')')
                    r += 1
            else:
                stack.append(')')
                r = 1
    if l == 0:
        right += r
    elif r == 0:
        left += l
    else:
        rev_r += r
        rev_l += l
        min_revr = min(min_revr, r)
        min_revl = min(min_revl, l)

if min_revr == 10**20:
    min_revr = 0
if min_revl == 10**20:
    min_revl = 0

if left+rev_l == rev_r+right and left >= min_revr and right >= min_revl:
    print('Yes')
else:
    print('No')


Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
from functools import reduce
from itertools import permutations

def f(s):
    while True:
        t = s.replace('()', '')
        if t == s:
            return s
        s = t

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

l = 0
r = 0
for s in S:
    t = s.count('(')
    l += t
    r += len(s) - t
if l != r:
    print('No')
    exit()

S = [s for s in map(f, S) if s != ""]

if len(S) == 0:
    print('Yes')
    exit()

lS = [s for s in S if s[0] == "("]
rS = [s for s in S if s[0] == ")"]

ld = {}
for s in lS:
    ld.setdefault(s, 0)
    ld[s] += 1

rd = {}
for s in rS:
    rd.setdefault(s, 0)
    rd[s] += 1

for k1 in ld:
    for k2 in rd.keys():
        if f(k1 + k2) != '':
            continue
        t = max(ld[k1], rd[k2])
        ld[k1] -= t
        rd[k2] -= t

if len(ld) == 0 and len(rd) == 0:
    print('Yes')
    exit()

SS = []
for k in ld:
    for i in range(ld[k]):
        SS.append(k)
for k in rd:
    for i in range(rd[k]):
        SS.append(k)

for ss in permutations(SS, len(SS)):
    t = reduce(lambda x, y: x + y, ss)
    if f(t) == '':
        print('Yes')
        exit()
print('No')


def scan(s):
    m = 0
    a = 0
    for c in s:
        if c == '(':
            a += 1
        elif c == ')':
            a -= 1
        m = min(m, a)
    return m, a


def key(v):
    m, a = v
    if a >= 0:
        return 1, m, a
    else:
        return -1, a - m, a

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

c = 0
for m, a in sorted([scan(s) for s in S], reverse=True, key=key):
    if c + m < 0:
        c += m
        break
    c += a

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


Verdicts: Runtime Error

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
import sys
input = sys.stdin.readline

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

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

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

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

P.sort(key=lambda a: a[0])
L.sort(key=lambda a: a[0], reverse=True)
P = [s for _, s in P]
L = [s for _, s in L]

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

if l == r and calc(ans) == 0:
    assert 0
    print('Yes')
else:
    print('No')


import sys
input = sys.stdin.readline

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

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

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

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

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

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

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


def kakko(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

plus = []
minus = []

for l, r in S:
    if l <= r:
        plus.append((l, r))
    else:
        minus.append((l, r))

plus.sort(key=lambda a: a[0])
minus.sort(key=lambda a: a[1], reverse=True)
M = 0
for l, r in (plus + minus):
    M -= l
    if M < 0:
        print('No')
        exit()
    M += r

print('Yes' if M == 0 else 'No')


Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: M * (z[0] + z[1]) - z[0]):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

from functools import reduce
n, *s = open(0).read().split()
u = []
for t in s:
    close_cnt = 0
    tmp = 0
    for c in t:
        tmp += (1 if c == '(' else -1)
        close_cnt = min(close_cnt, tmp)
    u.append((close_cnt, tmp - close_cnt))
M = 10**6 + 1
acc = 0
for a, b in sorted(u, key=lambda z: (- M - z[0] if sum(z)>= 0 else M - z[1])):
    if acc + a < 0:
        print("No")
        exit(0)
    else:
        acc += a + b
print(("No" if acc else "Yes"))

Verdicts: Wrong Answer

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        height = 0
        bottom = 0
        for c in s:
            if c == "(":
                height += 1
            else:
                height -= 1
                bottom = min(bottom, height)
        if height > 0:
            up_lines.append((bottom, height))
        else:
            down_lines.append((bottom-height, -height))
    up_lines.sort(reverse=True, key=lambda line: line.bottom)
    down_lines.sort(reverse=True, key=lambda line: line.bottom)
    left = 0
    for bottom, height in up_lines:
        if left + bottom < 0:
            print("No")
            return
        left += height
    right = 0
    for bottom, height in down_lines:
        if right + bottom < 0:
            print("No")
            return
        right += height
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()


def main():
    N = int(input())
    up_lines = []
    down_lines = []
    for i in range(N):
        s = input()
        height = 0
        bottom = 0
        for c in s:
            if c == "(":
                height += 1
            else:
                height -= 1
                bottom = min(bottom, height)
        if height > 0:
            up_lines.append((bottom, height))
        else:
            down_lines.append((bottom-height, -height))
    up_lines.sort(reverse=True, key=lambda line: line[0])
    down_lines.sort(reverse=True, key=lambda line: line[0])
    left = 0
    for bottom, height in up_lines:
        if left + bottom < 0:
            print("No")
            return
        left += height
    right = 0
    for bottom, height in down_lines:
        if right + bottom < 0:
            print("No")
            return
        right += height
    if left == right:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()


Verdicts: Runtime Error

Accepted
Problem: A **bracket sequence** is a string that is one of the following:    1. An empty string;   2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;   3. 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?

Submission attempts (in order):
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s:
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp = [-m, (s.count("(")-s.count(")"))-m]
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()

def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    S = [input() for _ in [0]*n]
    s2 = []
    s3 = []
    for s in S:
        temp = [0, 0]
        m = 0
        now = 0
        for i in s.strip('\n'):
            if i == "(":
                now += 1
            else:
                now -= 1
            m = min(m, now)
        temp = [-m, (s.count("(")-s.count(")"))-m]
        if temp[0] < temp[1]:
            s2.append(temp)
        else:
            s3.append(temp)
    s2.sort(key=lambda x: (x[0]))
    s3.sort(key=lambda x: (-x[1]))
    cnt = 0
    for i, j in s2:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    for i, j in s3:
        cnt -= i
        if cnt < 0:
            print("No")
            return
        cnt += j
    if cnt != 0:
        print("No")
        return
    print("Yes")


main()


Verdicts: Wrong Answer

Accepted