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:
MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
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):
        if j >= a:
            dp[i+1][j] = dp[i][j]*2 + dp[i][j-a]
        else:
            dp[i+1][j] = dp[i][j]*2
        dp[i+1][j] %= MOD
ans = dp[n][s]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# import itertools
# import numpy as np

n, s = list(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(0, n):
    for j in range(0, s+1):
        dp[i+1][j] += dp[i][j]*2 % mod

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


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

n, s = nm()
a = nl()
mod = 998244353
dp = [0]*(s+1)
dp[0] = 1
for i in range(n):
    v = a[i]
    for j in range(s, -1, -1):
        if j >= v:
            dp[j] = (dp[j] * 2 + dp[j-v]) % mod
        else:
            dp[j] = dp[j] * 2 % mod
print(dp[s])

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, s = map(int, input().split())
  a = [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(1, n+1):
    for j in range(s, -1, -1):
      dp[i][j] += dp[i-1][j]*2
      dp[i][j] %= mod
      if dp[i-1][j] and j+a[i-1] <= s:
        dp[i][j+a[i-1]] += dp[i-1][j]
        dp[i][j+a[i-1]] %= 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()))
dp = [[0 for i in range(s+1)] for j 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] = dp[i][j]*2
        if a[i] <= j:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= MOD
print(dp[n][s])

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(S+1)] for _ in range(N+1)]
# dp[i][j] Aiまでを使って、合計jを作る作り方
dp[0][0] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0] = pow(2,n,mod)
    MODINV2 = mod_inv(2,mod)
    ans = 0
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            dp[i+1][j] += dp[i][j-a[i]]*MODINV2
            dp[i+1][j] %= mod
        for j in range(s,-1,-1):
            if j == s:
                ans += dp[i+1][j]
                ans %= mod
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
def main():
    n,s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
    dp[0][0] = pow(2,n,mod)
    MODINV2 = mod_inv(2,mod)
    for i in range(n):
        for j in range(s,-1,-1):
            if j-a[i] < 0:
                continue
            dp[i+1][j] += dp[i][j-a[i]]*MODINV2
            dp[i+1][j] %= mod
        for j in range(s,-1,-1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
    print(dp[n][s]%mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    # morau
    for i, a in enumerate(A):
        dp[i][0] = pow(2, i, MOD)
            
        for j in range(S+1):
            if j >= a:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                dp[i+1][j] += dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] = 2 * dp[i][j]
                dp[i+1][j] %= MOD
                

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

Submission status: Time Limit Exceeded

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
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] += 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]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))
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] += 2*dp[i][j]
    dp[i+1][j] %= mod
    if j >=A[i]:
      dp[i+1][j] += dp[i][j-A[i]]
      dp[i+1][j] %= mod
print(dp[N][S]%mod)

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from collections import defaultdict

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353

    dp0 = [[]]
    ans = 0
    T  = [defaultdict(int, [(0, 1)])]
    for ai in A:
        tmp = []
        for t1 in T:
            t2 = t1.copy()
            for k, v in t1.items():
                if k + ai > S:
                    continue
                t2[k+ai] += v
                t2[k+ai] %= mod
            tmp.append(t2)

            ans += t2[S]
            ans %= mod

        T += tmp

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

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

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

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

print(dp[s] * pow(2, n - len(a), mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(3001)] for j in range(3001)]
#dp[X][S]=最後の物がX番目以下のもので、総和をSにしてくれる物の総数
dp[0][0]=1

mod=998244353

for i in range(N):
    w=A[i]
    for j in range(S+1):
        if j>=w:
            dp[i+1][j]+=(2*dp[i][j]+dp[i][j-w])
        else:
            dp[i+1][j]+=2*dp[i][j]
        dp[i+1][j]%=mod

print(dp[N][S]%mod)

Submission status: Time Limit Exceeded

Solution code:
def DP(A,N,S,M):
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0] = 1
    #dp[i][j]:要素数i個以下,i番目までで和がjである部分集合の個数
    for i in range(1,N+1):
        for j in range(S+1):
            dp[i][j] = 2 * dp[i-1][j]
            dp[i][j] %= M
            if j - A[i-1] >= 0:
                dp[i][j] += dp[i-1][j-A[i-1]]
                dp[i][j] %= M

    return dp[N][S]

def main():
    N,S = map(int,input().split())
    A = list(map(int,input().split()))
    M = 998244353

    ans = DP(A,N,S,M)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    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):
        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__":
    resolve()

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)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
  print(dp[s]%mod)
calc()

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(S+1)] for i in range(N+1)] #dp[i][j] = i番目まで見て重さjのものを取る方法
dp[0][0] = 1

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

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

print(dp[N][S])            

# print(dp)

Submission status: Time Limit Exceeded

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

dp = [[0]*(S+1) for i in range(N+1)]
dp[0][0] = 1
for i, a in  enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = 2*dp[i-1][s]
    if a <= s:
      dp[i][s] += dp[i-1][s-a]
    dp[i][s] %= 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)]
for i in range(n+1):
    dp[i][0] = 1
for i in range(1,n+1):
    x = a[i-1]
    for j in range(s+1):
        dp[i][j] = dp[i-1][j] * 2
        if dp[i][j] >= mod:
            dp[i][j] %= mod
    for j in range(x,s+1):
        if j >= x:
            dp[i][j] += dp[i-1][j-x]
            if dp[i][j] >= mod:
                dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
P = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for i in range(N+1)]
# dp = [[0]*(S+1) for i in range(N)]
# dp[i][j] i番目まで見た時に和がjになる組み合わせの個数
dp[0][0] = 1
for i in range(N):
    num = A[i]
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]*2
        if j-num >= 0:
            dp[i+1][j] += dp[i][j-num]
        dp[i+1][j] %= P
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353
class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=pow(2,n,MOD)
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]*pow(2,MOD-2,MOD)
        dp[i+1][j]%=MOD
print(dp[n][s])

Submission status: Time Limit Exceeded

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

dp = [[[] for i in range(S+1) ] for j in range(N+1)]
dp[0][0]=[0]
#print(dp)
for i in range(1,N+1):
  #print(i)
  a = A[i-1]
  for j in range(S+1):
    if len(dp[i-1][j])>0:
      dp[i][j] = list(dp[i-1][j])
    if j>=a:
      if len(dp[i-1][j-a]) > 0:
        if len(dp[i][j])>0:
          #print("add",i,j,i-1,j-a, [k+1 for k in dp[i-1][j-a]])
          dp[i][j] += [k+1 for k in dp[i-1][j-a]]
        else:
          #print("make",i,j,i-1,j-a, [k+1 for k in dp[i-1][j-a]])
          dp[i][j] = [k+1 for k in dp[i-1][j-a]]
last = dp[-1][-1]
ans = 0
for value in last:
  ans += 2**(N-value)
  ans %= 998244353
#print(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353
class mint:
    def __init__(self, x):
        if isinstance(x, int):
            self.x = x % MOD 
        elif isinstance(x, mint):
            self.x = x.x
        else:
            self.x = int(x) % MOD 
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )


n,s = map(int, input().split())
a = list(map(int, input().split()))
import copy
dp = [[mint(0)for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=mint(pow(2,n,MOD))
for i in range(n):
    for j in range(s+1):
        dp[i+1][j]=mint(dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]//2
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
ans = 0

inv_2 = pow(2, mod-2, mod)
dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0] = pow(2, n, mod)

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

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

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

Submission status: Time Limit Exceeded

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

dp = [[{} for i in range(S+1) ] for j in range(N+1)]
dp[0][0][0]=1
#print(dp)
for i in range(1,N+1):
  #print(i)
  a = A[i-1]
  if i==0:
    if a <= S:
      dp[i][a][1] = 1  
    continue
  for j in range(S+1):
    if len(dp[i-1][j])>0:
      for key, value in dp[i-1][j].items():
        dp[i][j][key] = value
    if j>=a:
      if len(dp[i-1][j-a]) > 0:
        for key, value in dp[i-1][j-a].items():
          if (key+1) in dp[i][j]:
            dp[i][j][key+1] += value
          else:
            dp[i][j][key+1] = value
last = dp[-1][-1]
ans = 0
for key, value in last.items():
  ans += 2**(N-key) * value
  ans %= 998244353
#print(last)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f_knapsack_for_all_subsets(MOD=998244353):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    # dp[i][j]: i 番目の要素を見たとき、和が j であるような場合の数
    dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
    dp[0][0] = 1  # インデックスの集合が空のとき、和は 0
    for i, a in enumerate(A):
        for j in range(S + 1):
            # editorial でいうところの選択肢 2, 3 に相当するので、2 倍
            dp[i + 1][j] += 2 * dp[i][j]
            dp[i + 1][j] %= MOD
            if j + a <= S:  # 選択肢 1
                dp[i + 1][j + a] += dp[i][j]
                dp[i + 1][j + a] %= MOD
    return dp[N][S]

print(f_knapsack_for_all_subsets())

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s, *a = map(int, read().split())
dp = [0] * (s + 1)
dp[0] = 1
mod = 998244353
for aa in a:
    for j in range(s, -1, -1):
        ss = j + aa
        if ss <= s:
            dp[ss] += dp[j]
            dp[ss] %= mod
        dp[j] *= 2
        dp[j] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, S = LI()
A = LI()

MOD = 998244353


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, s = map(int, readline().split())
a = list(map(int, readline().split()))
dp = [[0] * (s + 2) for _ in range(n + 1)]
dp[0][0] = 1
mod = 998244353
for i, aa in enumerate(a):
    for j in range(s + 1):
        ss = j + aa
        dp[i + 1][min(j + aa, s + 1)] += dp[i][j]
        dp[i + 1][j] += dp[i][j] * 2
        dp[i + 1][j] %= mod
print(dp[-1][-2])

Submission status: Time Limit Exceeded

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

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

    @lru_cache(maxsize=None)
    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
        val = (g(n - 1, S) * 2 + g(n - 1, S - A[n])) % mod
        if A[n] == S: val += 1
        #print("g({},{})={}".format(n, S, val))
        return val % mod
    
    print(g(N - 1, 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

temp = [1] + [0] * s
for i in range(n):
    temp2 = [0] * (s + 1)
    for j in range(s + 1):
        temp2[j] += temp[j] * 2
        temp2[j] %= mod
    for j in range(s + 1 - a[i]):
        temp2[j + a[i]] += temp[j]
        temp2[j + a[i]] %= mod
    temp = temp2
print(temp[s])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    x = a[i-1]
    for j in range(s+1):
        if j == 0:
            dp[i][j] += dp[i-1][j] + 1
            dp[i][j] %= mod
        elif dp[i-1][j]:
            dp[i][j] += dp[i-1][j] * 2
            dp[i][j] %= mod
        if j - x < 0:
            continue
        if j - x == 0:
            dp[i][j] += pow(2, dp[i-1][j-x])
            dp[i][j] %= mod
        elif dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]
            dp[i][j] %= mod
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    x = a[i-1]
    for j in range(s+1):
        if j == 0:
            dp[i][j] += dp[i-1][j] + 1
            dp[i][j] %= mod
        elif dp[i-1][j]:
            dp[i][j] += dp[i-1][j] * 2
            dp[i][j] %= mod
    for j in range(s+1):
        if j - x < 0:
            continue
        if j - x == 0:
            dp[i][j] += pow(2, dp[i-1][j-x])
            dp[i][j] %= mod
        elif dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]
            dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,S = map(int,S().split())
A = [0] + LI()
mod = 998244353

from collections import defaultdict

dp = defaultdict(int)

# dp[i][j] = A_1からA_iまでを用いて和がj

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

print(dp[(N,S)])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, s = LI()
a = LI()

dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1, n+1):
    x = a[i-1]
    for j in range(s+1):
        if j == 0:
            dp[i][j] += dp[i-1][j] + 1
        elif dp[i-1][j]:
            dp[i][j] += dp[i-1][j] * 2
            dp[i][j] %= mod
    for j in range(s+1):
        if j - x < 0:
            continue
        if j - x == 0:
            dp[i][j] += 2**dp[i-1][j-x]
            dp[i][j] %= mod
        elif dp[i-1][j-x]:
            dp[i][j] += dp[i-1][j-x]
            dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
# 100% TLE

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

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


ans = 0
for j in range(N+1):
    ans += dp[-1][j][-1] * pow(2, N-j, MOD) % MOD
    ans %= MOD

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 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
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])

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().split())
mod=998244353
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=pow(2,n,mod)
for i in range(n):
  for j in range(s+1):
    dp[i+1][j]+=dp[i][j]
    dp[i+1][j]%=mod
    if j+a[i]<=s:
      dp[i+1][j+a[i]]+=dp[i][j]*(mod+1)//2
      dp[i+1][j+a[i]]%=mod
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
sumA=sum(A)

dp=[defaultdict(int) for n in range(3001)]
for n in range(N):
    a=A[n]

    for s in range(max(0,S-sumA),S+1)[::-1]:
        if s+a<=S:
            for h in dp[s]:
                dp[s+a][h+1]+=dp[s][h]
    dp[a][1]+=1
    sumA-=a
c=0
for a in dp[S]:
    c+=pow(2,N-a,mod)*dp[S][a]
    c%=mod
print(c)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
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])

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, e in enumerate(a, 1):
    for j in range(s + 1):
        dp[i][j] += 2 * dp[i-1][j]
        if j - e >= 0:
            dp[i][j] += dp[i-1][j-e]

        dp[i][j] %= mod

ans = dp[n][s]
print(ans)