Problem:


Score : 600 points

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.

For a non-empty subset T of the set \{1, 2, \ldots , N \}, let us define f(T) as follows:

f(T) is the number of different non-empty subsets \{x_1, x_2, \ldots , x_k \} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(T) over all 2^N-1 subsets T of \{1, 2, \ldots , N \}. Since the sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(T) modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

6

For each T, the value of f(T) is shown below. The sum of these values is 6.

f(\{1\}) = 0

f(\{2\}) = 0

f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)

f(\{1, 2\}) = 1 (\{1, 2\})

f(\{2, 3\}) = 1 (\{3\})

f(\{1, 3\}) = 1 (\{3\})

f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

3296



Sample input:
3 4
2 2 4


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] += 2*dio[j]
            di[j] %= mod
        for j in range(ai, s+1):
            di[j] += 2*dio[j] + dio[j-ai]
            di[j] %= mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] += 2*dio[j]
            di[j] %= mod
        for j in range(ai, s+1):
            di[j] += 2*dio[j]
            di[j] += dio[j-ai]
            di[j] %= mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(s+1):
            di[j] += 2*dio[j]
            di[j] %= mod
            if j >= ai:
                di[j] += dio[j-ai]
                di[j] %= mod
        dp[i] = di
    print(dp[n][s])
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

N, S = map(int, input().split(' '))
A = (0, *map(int, input().split(' ')))

dp = []
for _ in range(N + 1):
    dp.append([0] * (S + 1))

dp[0][0] = 1

for i in range(1, N + 1):
    a = A[i]
    for j in range(S + 1):
        dp[i][j] = 2 * dp[i - 1][j] % MOD
        if j >= a:
            dp[i][j] += dp[i - 1][j - a]
            dp[i][j] %= MOD

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod

        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= mod

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]

  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub == 0:
        dp[i + 1][j] += 2 ** (i) % 998244353
      if sub > 0 and dp[i][sub]:
        dp[i + 1][j] += dp[i][sub]
  #print(dp)
  print(dp[length][target] % 998244353)
  
solve(N, S, A)

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
MOD=998244353
dp=[[0 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]*2
        dp[i+1][j]%=MOD
        if j+A[i]<=S:
            dp[i+1][j+A[i]]+=dp[i][j]
            dp[i+1][j+A[i]]%=MOD
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]

  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub == 0:
        dp[i + 1][j] += 2 ** (i)
      if sub > 0 and dp[i][sub]:
        dp[i + 1][j] += dp[i][sub]
  #print(dp)
  print(dp[length][target] % 998244353)
  
solve(N, S, A)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import numba
from typing import List


def solver(N: int, S: int, A) -> int:
    dp = [[0] * (S+1) for _ in range(N+1)]

    dp[0][0] = 1
    MOD = 998244353
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j] += 2 * dp[i][j]
            dp[i+1][j] %= MOD
            if j + A[i] <= S:
                dp[i+1][j+A[i]] += dp[i][j]
                dp[i+1][j+A[i]] %= MOD
    return dp[N][S]


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    ans = solver(N, S, A)
    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    dp = np.zeros((N+1, S+1), dtype=np.int64)

    dp[0,0] = 1
    MOD = 998244353
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += 2 * dp[i, j]
            dp[i+1, j] %= MOD
            if j + A[i] <= S:
                dp[i+1, j+A[i]] += dp[i, j]
                dp[i+1, j+A[i]] %= MOD
    print(dp[N,S])
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    N, S = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]

    dp = np.zeros((N+1, S+1), dtype=int)

    dp[0,0] = 1
    MOD = 998244353
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += 2 * dp[i, j]
            dp[i+1, j] %= MOD
            if j + A[i] <= S:
                dp[i+1, j+A[i]] += dp[i, j]
                dp[i+1, j+A[i]] %= MOD
    print(dp[N,S])
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((S+1), dtype=int)
    dp[0] = 2
    if An[0] <= S:
        dp[An[0]] = 1

    for n in range(1, N):
        for k in range(S, -1, -1):
            if k + An[n] <= S:
                dp[k+An[n]] = (dp[k+An[n]] + dp[k]) % 998244353
            dp[k] = (dp[k] * 2) % 998244353

    print(dp[S])
                
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N, S = map(int, readline().split())
A = list(int(x) for x in readline().split())
MOD = 998244353

dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        # 1,2のケース。jが変わらない遷移が2通りある。
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % MOD
        # 3のケース。j+A[i] <= Sならば、j+A[i]に遷移する。
        if j + A[i] <= S:
            dp[i+1][j+A[i]] = (dp[i+1][j+A[i]] + dp[i][j]) % MOD
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((2, S+1), dtype=int)
    dp[0, 0] = 2
    if An[0] <= S:
        dp[0, An[0]] = 1

    for n in range(1, N):
        dp[(n)%2, :] *= 0
        for k in range(S, -1, -1):
            dp[n%2, k] = (dp[n%2, k] + dp[(n-1)%2, k] * 2) % 998244353
            if k + An[n] > S:
                continue
            dp[n%2, k+An[n]] = (dp[n%2, k+An[n]] + dp[(n-1)%2, k]) % 998244353

    print(dp[(N-1)%2, S])
                
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = np.zeros((2, S+1), dtype=int)
    dp[0, 0] = 2
    if An[0] <= S:
        dp[0, An[0]] = 1

    for n in range(1, N):
        dp[(n)%2, :] *= 0
        for k in range(S + 1):
            dp[n%2, k] = (dp[n%2, k] + dp[(n-1)%2, k] * 2) % 998244353
            if k + An[n] > S:
                continue
            dp[n%2, k+An[n]] = (dp[n%2, k+An[n]] + dp[(n-1)%2, k]) % 998244353

    print(dp[(N-1)%2, S])
                
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(int(x) for x in input().split())
MOD = 998244353

dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        # 1,2のケース。jが変わらない遷移が2通りある。
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % MOD
        # 3のケース。j+A[i] <= Sならば、j+A[i]に遷移する。
        if j + A[i] <= S:
            dp[i+1][j+A[i]] = (dp[i+1][j+A[i]] + dp[i][j]) % MOD
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __repr__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md=998244353

def main():
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    dp[0]=mint(1)
    for a in aa:
        for i in range(s,-1,-1):
            pre=dp[i]
            if pre==0:continue
            dp[i]+=pre
            if i+a<=s:dp[i+a]+=pre
    print(dp[s])

main()

Submission status: Time Limit Exceeded

Solution code:
"""
Asの部分集合Tの部分集合Uについて考える

1. Tに属さない
2. Tに属し、Uに属さない
3. Tに属し、Uに属す

の3通り考えられる。
i番目までにおいて、部分集合Uの和がkになる⇨dp[i][k]

遷移としては
dp[i+1][k] = dp[i][k] * 2 # 1.2
dp[i+1][k+A[i]] += dp[i][k]
"""
n,s = map(int, input().split())
As  = list(map(int, input().split()))
mod = 998244353
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    a = As[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        if j + a <= s:
            dp[i+1][j+a] += dp[i][j]
        dp[i+1][j] %= mod
    
            

ans = 0
print(dp[n][s]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (S + 1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j + a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
print(dp[N][S])

Submission status: Time Limit Exceeded

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


def read():
    N, S = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, S, A


def solve(N, S, A, MOD=998244353):
    dp = [0 for j in range(S+1)]
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

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


def read():
    N, S = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, S, A


def solve(N, S, A, MOD=998244353):
    A = list(sorted(A))
    dp = [0 for j in range(S+1)]
    dp[0] = 1
    for i in range(N):
        for j in range(S, -1, -1):
            v = 2 * dp[j]
            if j - A[i] >= 0:
                v += dp[j-A[i]]
            dp[j] = v % MOD
    return dp[S]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10**9)
mod = 998244353

def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    d = {}

    def g(n, S):
        if S < 0: return 0
        if S == 0: return pow(2, n + 1, mod) - 1
        if n == 0 and S == A[0]: return 1
        if n == 0: return 0
        if (n, S) in d: return d[(n, S)]
        val = (g(n - 1, S) * 2 + g(n - 1, S - A[n])) % mod
        if A[n] == S: val += 1
        d[(n, S)] = val % mod
        return d[(n, S)]
    
    print(g(N - 1, S))

    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

n,s = map(int, input().split())
al = list(map(int, input().split()))

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    a = al[i]
    for j in range(s+1):
        dp[i+1][j] += 2*dp[i][j]
        dp[i+1][j] %= mod

        if j+a<=s:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= mod

print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
A = list(map(int, input().split()))

MOD = 998244353
 
# dp[i][j] = i 番目までの選択をして、1 つめの選択肢を選んだ k に対する ak の和が j であるような場合の数
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(n):
  for j in range(s + 1):
    dp[i + 1][j] += dp[i][j] * 2
    dp[i + 1][j] %= MOD
    if j + A[i] <= s:
      dp[i + 1][j + A[i]] += dp[i][j]
      dp[i + 1][j + A[i]] %= MOD

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n,s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(s+1):
        if j - A[i] >= 0:
            dp[i+1][j]=(dp[i][j]*2+dp[i][j-A[i]])%mod
        else:
            dp[i+1][j]=(dp[i][j]*2)%mod
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

N, S = MAP()
A = LIST()

dp = list2d(N+1, S+1, 0)
dp[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j+a <= S:
            dp[i+1][j+a] += dp[i][j]
            dp[i+1][j+a] %= MOD
ans = dp[N][S]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for s in range(S+1):
        if s-A[i] >= 0:
            dp[i+1][s] = (dp[i][s] * 2 + dp[i][s-A[i]]) % MOD
        else:
            dp[i+1][s] = dp[i][s] * 2 % MOD
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:

def solve(N,S,A):
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    mod = 998244353
    for i, a in enumerate(A, 1):
        for s in range(S+1):
            if s-a >= 0:
                dp[i][s] = (dp[i-1][s] * 2 + dp[i-1][s-a]) % mod
            else:
                dp[i][s] = dp[i-1][s] * 2 % mod
    print(dp[N][S])

N, S = map(int, input().split())
A = list(map(int, input().split()))
solve(N,S,A)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    aa = LI()

    dp = [0] * (s+1)
    dp[0] = 1
    for a in aa:
        np = [0] * (s+1)
        for i in range(s-a,-1,-1):
            np[i+a] = dp[i]
        for i in range(s+1):
            dp[i] *= 2
            dp[i] += np[i]
            dp[i] %= mod2

    return dp[-1]

print(main())

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
a = input().split()
count = 0
for i in range(2 ** n):
  bit_list = []
  for j in range(n):
    if i >> j & 1:
      bit_list.append(int(a[j]))
  #print(bit_list, sum(bit_list), s)
  if bit_list != [] and sum(bit_list) == s:
    count += 2 ** (n - len(bit_list))
    count %= 998244353
      #print(bit_list, subset_list, total)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return [type(i) for i in input().split()]
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

# Implementation
class ModInt:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
    
    def __add__(self, o):
        return ModInt((self.n + o.n) % self.MOD, self.MOD)

    def __sub__(self, o):
        return ModInt((self.n - o.n + self.MOD) % self.MOD, self.MOD)

    def __mul__(self, o):
        return ModInt((self.n * o.n) % self.MOD, self.MOD)

    def __iadd__(self, o):
        self.n = (self.n + o.n) % self.MOD
        return self

    def __isub__(self, o):
        self.n = (self.n - o.n + self.MOD) % self.MOD
        return self

    def __imul__(self, o):
        self.n = (self.n * o.n) % self.MOD
        return self

    def __str__(self): return str(self.n)

MOD = 998244353
N, S = read_tupple()
A = read_array()

dp = [[ModInt(0, MOD) for j in range(S+1)] for i in range(N+1)]
dp[0][0] = ModInt(1, MOD)
for i in range(N):
    for j in range(S+1):
        dp[i + 1][j] += ModInt(2, MOD) * dp[i][j]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
# Import
from collections import deque
import math

# I/O
def read(): return input()
def read_int(): return int(input())
def read_array(type=int): return list(map(type, input().split()))
def read_tupple(type=None):
    tmp = input().split()
    if type is None: return map(int, tmp)
    assert len(tmp) == len(type)
    return [type[i](tmp[i]) for i in range(len(tmp))]

# Implementation
class ModInt:
    def __init__(self, n, MOD):
        self.n = n
        self.MOD = MOD
    
    def __add__(self, o):
        return ModInt((self.n + o.n) % self.MOD, self.MOD)

    def __sub__(self, o):
        return ModInt((self.n - o.n + self.MOD) % self.MOD, self.MOD)

    def __mul__(self, o):
        return ModInt((self.n * o.n) % self.MOD, self.MOD)

    def __iadd__(self, o):
        self.n = (self.n + o.n) % self.MOD
        return self

    def __isub__(self, o):
        self.n = (self.n - o.n + self.MOD) % self.MOD
        return self

    def __imul__(self, o):
        self.n = (self.n * o.n) % self.MOD
        return self

    def __str__(self): return str(self.n)

MOD = 998244353
N, S = read_tupple()
A = read_array()

dp = [[ModInt(0, MOD) for j in range(S+1)] for i in range(N+1)]
dp[0][0] = ModInt(1, MOD)
for i in range(N):
    for j in range(S+1):
        dp[i + 1][j] += ModInt(2, MOD) * dp[i][j]
        if j - A[i] >= 0:
            dp[i + 1][j] += dp[i][j - A[i]]
print(dp[N][S])

Submission status: Time Limit Exceeded

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

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[[0]*(s+1) for _ in range(n+1)]
  dp[0][0]=1
  for i in range(1,n+1):
    val=arr[i-1]
    for j in range(s,-1,-1):
      dp[i][j]=2*dp[i-1][j]
      dp[i][j]%=mod
      if j-val>=0 and dp[i-1][j-val]!=0:
        dp[i][j]+=dp[i-1][j-val]
  print(dp[n][s]%mod)
calc()

Submission status: Time Limit Exceeded

Solution code:
# 厳しい
n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [[0]*(n+1) for _ in range(W_MAX+1)]
dp[0][0] = 1

for i in range(n):
    a = A[i]
    for j in reversed(range(W_MAX+1)):
        for k in range(n):
            if W_MAX < j+a:
                continue
            dp[j+a][k+1] += dp[j][k]

ans = 0
for k in range(1, n+1):
    cnt = dp[-1][k]
    ans += cnt*pow(2, n-k, MOD)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
mod = 998244353
ans = 0

def DFS(n, m, t):
  global ans
  if t > S:
    return
  if t == S:
    ans = (ans+pow(2,N-m,mod))%mod
    return
  while n < N:
    DFS(n+1,m+1,t+A[n])
    n += 1
  return
#

DFS(0,0,0)
print(ans)
#

Submission status: Time Limit Exceeded

Solution code:
# よくわからんので、O(N**3)をやってみる
n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
W_MAX = s
dp = [[[0]*(n+1) for _ in range(W_MAX+1)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(1, n+1):
    a = A[i-1]
    for j in range(W_MAX+1):
        for k in range(n):
            dp[i][j][k] += dp[i-1][j][k]
            if W_MAX < j+a:
                continue
            dp[i][j+a][k+1] += dp[i-1][j][k]

ans = 0
for k in range(1, n+1):
    cnt = dp[-1][-1][k]
    ans += cnt*pow(2, n-k, MOD)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
ans = 0

def DFS(n, m, t):
  global ans
  if t > S:
    return
  if t == S:
    ans = (ans+pow(2,N-m,mod))%mod
    return
  while n < N:
    DFS(n+1,m+1,t+A[n])
    n += 1
  return
#

DFS(0,0,0)
print(ans)
#

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)

MOD = 998244353

n, s = map(int, input().split())
la = [int(i) for i in input().split()]


dks = [[None] * (s + 1) for _ in range(n)]


def getks(i=0, t=s):
    if t < 0:
        return 0
    elif i == n:
        return int(t == 0)
    elif dks[i][t] is not None:
        return dks[i][t]
    else:
        ks0 = getks(i + 1, t)
        ks1 = getks(i + 1, t - la[i])
        ks = (2 * ks0 + ks1) % MOD
        dks[i][t] = ks
        return ks


answer = getks()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    mod = 998244353
    dp = np.zeros((n + 1, s + 1), dtype=int)
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)

MOD = 998244353

n, s = map(int, input().split())
la = [int(i) for i in input().split()]


dks = [[None] * (s + 1) for _ in range(n)]


def getks(i=0, t=s):
    if t < 0:
        return 0
    elif i == n:
        return int(t == 0)
    elif dks[i][t] is not None:
        return dks[i][t]
    else:
        ks = 2 * getks(i + 1, t) + getks(i + 1, t - la[i])
        ks %= MOD
        dks[i][t] = ks
        return ks


answer = getks()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)

MOD = 998244353

n, s = map(int, input().split())
la = [int(i) for i in input().split()]


dks = [[None] * (s + 1) for _ in range(n)]


def getks(i=0, s=s):
    if s < 0:
        return 0
    elif i == n:
        return int(s == 0)
    elif dks[i][s] is not None:
        return dks[i][s]
    else:
        ks = 2 * getks(i + 1, s) + getks(i + 1, s - la[i])
        ks %= MOD
        dks[i][s] = ks
        return ks


answer = getks()
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % 998244353
            else:
                dp[i + 1][j] = (dp[i][j] * 2 + dp[i][j - ai]) % 998244353
    print(dp[n][s])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, s = map(int, input().split())
    a = sorted([int(i) for i in input().split()])
    mod = 998244353
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        ai = a[i]
        for j in range(s + 1):
            if j < ai:
                dp[i + 1][j] = dp[i][j] * 2 % mod
            else:
                dp[i + 1][j] = (dp[i][j] * 2 % mod + dp[i][j - ai]) % mod
    print(dp[n][s])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
##WA 和がSになる組み合わせを列挙しようとしたけど無理だった。
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
mod = 998244353
n,s = ma()
A = list(ma())
dp = [[0]*(s+1) for i in range(n+1)]#dp[i][j]はi番目までの要素を用いてjになるような場合の数
dp[0][0] = 1
for i in range(n):
    a = A[i]
    for j in range(s+1):
        dp[i+1][j] =(dp[i][j]*2)%mod
        if a<=j:
            dp[i+1][j] = (dp[i][j-a] +dp[i+1][j]) %mod

print(dp[n][s])
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
dp=[[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=1

for i in range(n):
    for c in range(s+1):
        if c>=A[i]:
            dp[i+1][c]=(2*dp[i][c]+dp[i][c-A[i]])%mod
        else:
            dp[i+1][c]=(2*dp[i][c])%mod

print(dp[n][s]%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

#d = [[0]*3001 for _ in range(3001)]
d=np.zeros((3001,3001))
d[0][0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    for j in range(S+1):
        d[i][j] += 2*d[i-1][j]
        if Ai <= j:
            d[i][j] += d[i-1][j-Ai]
        d[i][j] %= MOD
print(int(d[N][S]))

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
As=list(map(int,input().split()))

MOD=998244353

d = [[0]*3001 for _ in range(3001)]
d[0][0]=1

for i in range(1,N+1):
    Ai=As[i-1]
    for j in range(S+1):
        d[i][j] += 2*d[i-1][j]
        if Ai <= j:
            d[i][j] += d[i-1][j-Ai]
        d[i][j] %= MOD
print(d[N][S])

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

def main():
  dp = [0]*(S+1)
  dp[0] = 1
  for i in range(1, N+1):
    p = [0]*(S+1)
    dp, p = p, dp
    for j in range(0, S+1):
      dp[j] += 2*p[j]
      dp[j] %= MOD
      if j-A[i-1] >= 0:
        dp[j] += p[j-A[i-1]]
        dp[j] %= MOD
  print(dp[S])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
def main():
  dp[0][0] = 1
  for i in range(1, N+1):
    for j in range(0, S+1):
      dp[i][j] += 2*dp[i-1][j]
      dp[i][j] %= MOD
      if j-A[i-1] >= 0:
        dp[i][j] += dp[i-1][j-A[i-1]]
        dp[i][j] %= MOD
  print(dp[N][S])

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
def main():
  dp[0][0] = 1
  for i in range(1, N+1):
    for j in range(0, S+1):
      dp[i][j] += (2*dp[i-1][j])%MOD
      dp[i][j] %= MOD
      if j+A[i-1] <= S:
        dp[i][j+A[i-1]] += dp[i-1][j]%MOD
        dp[i][j+A[i-1]] %= MOD
  print(dp[N][S])

if __name__ == "__main__":
  main()