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:
import os
import sys
from io import BytesIO, IOBase
from sys import stdin
def input():
    return stdin.readline()

def main():
    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(1,N+1) : 
        for j in range(S + 1) : 
            if(j==0):
                dp[i][j]=2**i
            else:
                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]%mod)
    


# fast-io region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


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

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

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

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

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

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

    for i in range(1, N+1):
        xi = X[i-1]
        for j in range(S+1):
            # xi を U に加えない場合
            dp[i][j] += dp[i-1][j]*2 # T に加える／加えない
            dp[i][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i][j+xi] += dp[i-1][j]
            dp[i][j+xi] %= MOD

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

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

    for i in range(1, N+1):
        xi = X[i-1]
        for j in range(S+1):
            # xi を U に加えない場合
            dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない
            dp[i][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i][j+xi] += dp[i-1][j] % MOD
            dp[i][j+xi] %= MOD

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

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

    for i in range(1, N+1):
        xi = X[i-1]
        for j in range(S+1):
            # xi を U に加えない場合
            dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない

            # xi を U に加える場合
            if j+xi > S: continue
            dp[i][j+xi] += dp[i-1][j] % MOD

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

MOD = 998244353

N, S = map(int, input().split())
X = [int(x) for x in sys.stdin.readline().split()]

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

for i in range(1, N+1):
    xi = X[i-1]
    for j in range(S+1):
        # xi を U に加えない場合
        dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない

        # xi を U に加える場合
        if j+xi > S: continue
        dp[i][j+xi] += dp[i-1][j] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    import numpy as np
    mod = 998244353
    dp = np.zeros((N+1, S+1), int)
    #dp[i, j]を、A[0]...A[i]までを使って、Tの空でない部分集合
    #{x_1, x_2, ..., x_k}であって、Ax_1 + A_x_2 + ... + A_x_k = jを満たすものの個数とする。
    dp[0, 0] = 1
    #iまででjが作られている時、i+1ではA[i]がどのような値であっても、部分集合としてjは作れる。
    #iまででjが作られない時、j-A[i]が作られていれば、A[i]を足せばjは作れる。
    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]:
                dp[i+1, j] += dp[i, j-A[i]]
                dp[i+1, j] %= mod
                    
    print(dp[N][S] % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    #output
    import numpy as np
    mod = 998244353
    dp = np.zeros((N+1, S+1), int)
    #dp[i, j]を、A[0]...A[i]までを使って、Tの空でない部分集合
    #{x_1, x_2, ..., x_k}であって、Ax_1 + A_x_2 + ... + A_x_k = jを満たすものの個数とする。
    dp[0, 0] = 1
    #iまででjが作られている時、i+1ではA[i]がどのような値であっても、部分集合としてjは作れる。
    #iまででjが作られない時、j-A[i]が作られていれば、A[i]を足せばjは作れる。
    for i in range(N):
        for j in range(S+1):
            dp[i+1, j] += dp[i, j] * 2 % mod
            if j >= A[i]:
                dp[i+1, j] += dp[i, j-A[i]]
                dp[i+1, j] %= mod
                    
    print(dp[N][S] % mod)

    #N = 1のときなどcorner caseを確認！
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]*(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] = dp[i][j]*2%mod
        if a[i]<=j: dp[i+1][j] = (dp[i+1][j]+dp[i][j-a[i]])%mod
        dp[i+1][j] %= mod
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
import sys
MOD = 998244353


def main():
    input = sys.stdin.buffer.readline
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[None] * (s + 1) for _ in range(n + 1)]
#     dp[i][j]:=集合{1..i}の空でない部分集合T全てについて,和がjとなる部分集合の個数の和
    for i in range(n + 1):
        for j in range(s + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
                continue
            if j > a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]
            elif j == a[i - 1]:
                dp[i][j] = dp[i - 1][j] * 2 + pow(2, i - 1, MOD)
            else:
                dp[i][j] = dp[i - 1][j] * 2
            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()))
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] = 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:
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]
      dp[i][j]%=mod
print(dp[n][s])

Submission status: Time Limit Exceeded

Solution code:
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):
    var = arr[i - 1]
    for j in range(s, -1, -1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))

Submission status: Time Limit Exceeded

Solution code:
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):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = np.zeros((n + 1, s + 1))
dp[0, 0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i, j] = 2 * dp[i - 1, j]
        dp[i, j] %= mod
        if j - var >= 0 and dp[i - 1, j - var] != 0:
            dp[i, j] += dp[i - 1, j - var]
            dp[i, j] %= mod
print(int(dp[n, s]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = np.zeros((n + 1, s + 1))
dp[0, 0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(s, -1, -1):
        dp[i, j] = 2 * dp[i - 1, j]
        dp[i, j] %= mod
        if j - var >= 0 and dp[i - 1, j - var] != 0:
            dp[i, j] += dp[i - 1, j - var]
            dp[i, j] %= mod
print(int(dp[n, s]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = np.zeros((n + 1, s + 1))
dp[0, 0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i, j] = 2 * dp[i - 1, j]
        dp[i, j] %= mod
        if j - var >= 0 and dp[i, j - var] != 0:
            dp[i, j] += dp[i - 1, j - var]
            dp[i, j] %= mod
print(int(dp[n, s]))

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
import numpy as np
dp = np.array([[2**i%mod]+[0]*(S) for i in range(N+1)])

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

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[2**i%mod]+[0]*(S) for i in range(N+1)]

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

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[2**i%mod]+[0]*(S) for i in range(N+1)]

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
As = list(map(int, input().split()))
mod = 998244353
dp = [[2**i%mod]+[0]*(S) for i in range(N+1)]

for i in range(1, N+1):
    a = As[i-1]
    for s in range(1, S+1):
        dp[i][s] += max(0, dp[i-1][s])*2
        if s-a>=0:
            dp[i][s] += dp[i-1][s-a]
        dp[i][s] %= mod
print(dp[-1][-1]%mod)

Submission status: Time Limit Exceeded

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

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

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[n][s])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,S,*A = map(int, open(0).read().split())
dp = [[0] * (S+1) for _ in range(N+1)]
dp[0][0] = 1
appeared = set([0])
for i in range(1,N+1):
    temp = A[i-1]
    ts = set()
    for x in appeared:
        dp[i][x] += (dp[i-1][x]*2) % 998244353
        if temp + x <= S:
            dp[i][temp+x] += dp[i-1][x]
            if temp + x not in appeared:
                ts.add(temp+x)
    appeared |= ts
print(dp[N][S]%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
	import sys
	sys.setrecursionlimit(10**7)
	mod=998244353
	n,s=map(int,input().split())
	a=list(map(int,input().split()))
	from functools import lru_cache
	@lru_cache(maxsize=None)
	def dfs(x,y):
		if x==0:
			if y==0:
				return 1
			else:
				return 0
		r=dfs(x-1,y)*2%mod
		if x>0:
			if y-a[x-1]>=0:
				r+=dfs(x-1,y-a[x-1])
		r%=mod
		return r
	print(dfs(n,s))
main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = {0: 1}
for n in range(N):
    next_table = dict()
    for s, now in table.items():
        next_table[s] = (next_table.get(s, 0) + now * 2) % MOD
        if s + A[n] <= S:
            next_table[s + A[n]] = (next_table.get(s + A[n], 0) + now) % MOD
    table = next_table
print(table.get(S, 0))

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, S = map(int, input().split())
A = tuple(map(int, input().split()))
table = [[0] * (S + 1) for _ in range(N + 1)]
table[0][0] = 1
for n in range(N):
    for s in range(S + 1):
        now = table[n][s]
        table[n + 1][s] = (table[n + 1][s] + now * 2) % MOD
        if s + A[n] <= S:
            table[n + 1][s + A[n]] = (table[n + 1][s + A[n]] + now) % MOD
print(table[N][S])

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):
	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:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n, s = map(int,input().split())
    a = list(map(int, input().split()))
    dp = [[0] * (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] += dp[i][j] * 2 % 998244353
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]
            dp[i + 1][j] %= 998244353
            
    print(dp[n][s])
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
L = [0 for _ in range(S+1)]
L[0] = 1
F = {0}
for i in range(N):
  X = [[i, L[i]] for i in F]
  for j in F:
    L[j] *= 2
    L[j] %= mod
  for j in X:
    if A[i] + j[0] <= S:
      L[A[i]+j[0]] += j[1]
      L[A[i]+j[0]] %= mod
      F.add(A[i]+j[0])
print(L[S])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    ddp = dp * 2
    for ss in range(s,a[i]-1,-1):
        ddp[ss] += dp[ss-a[i]]%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD


print(int(dp[s]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    ddp = dp * 2
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            ddp[ss] += dp[ss-a[i]]%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
    dp = ddp % MOD


print(int(dp[s]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 998244353

dp = np.zeros(s+1) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            dp[ss] = (dp[ss]*2 + dp[ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[ss] = dp[ss]*2 % MOD

print(int(dp[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) #動的計画法を用いる
dp[0] = 1

for i in range(n):
    for ss in range(s,-1,-1):
        if(ss >= a[i]):
            dp[ss] = (dp[ss]*2 + dp[ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[ss] = dp[ss]*2 % MOD

print(dp[s])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n, s = map(int, input().split())
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i, a in enumerate(map(int, input().split())):
  for j in range(s + 1):
    dp[i+1][j] = (dp[i][j] * 2) % mod
    if j >= a:
      dp[i+1][j] = (dp[i+1][j] + dp[i][j-a]) % 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 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 = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 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] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)

Submission status: Time Limit Exceeded

Solution code:
def get_integral_value_combination(list, target):
    def a(idx, l, r, t):
        s = sum(l)
        if t == s: r.append(l)
        elif t < s: return
        for u in range(idx, len(list)):
            a((u + 1), l + [list[u]], r, t)
        return r
    return a(0, [], [], target)
N, S = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
ind = get_integral_value_combination(A, S)
for i in ind:
    ans += 2 ** (N - len(i))
ans %= 998244353
print(ans)

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)]
  dp[0][0] = 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
      dp[i + 1][j] %= 998244353
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
        dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
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]*(s+1)
dp[0] = pow(2, n, MOD)
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(s+1)):
        if s < j+a:
            continue
        dp[j+a] += dp[j]*inv_2 % MOD

print(dp[-1] % MOD)

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]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2
        dp[j+a] %= MOD

print(dp[-1]*pow(2, n, MOD) % MOD)

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]*(W_MAX+1)
dp[0] = 1
inv_2 = pow(2, MOD-2, MOD)
for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*inv_2

print(dp[-1]*pow(2, n, MOD) % MOD)

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]*(W_MAX+1)
dp[0] = 1

for a in A:
    for j in reversed(range(W_MAX+1)):
        if W_MAX < j+a:
            continue
        dp[j+a] += dp[j]*pow(2, MOD-2, MOD)

print(dp[-1]*pow(2, n, MOD) % MOD)

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

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0]*(S+2) for i in range(N+1)]
dp[0][0] = 1
mod = 998244353
for i,a in enumerate(A):
    for j in range(S+1):
        if j-a >= 0:
            dp[i+1][j] = (dp[i][j]*2+dp[i][j-a])%mod
        else:
            dp[i+1][j] = dp[i][j]*2%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 i in range(n+1)] #動的計画法を用いる
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2%MOD + dp[i][ss-a[i]])%MOD #非常に大きな数になると考えられるため先にMOD計算を行う
        else:
            dp[i+1][ss] = dp[i][ss]*2 % 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 i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 + dp[i][ss-a[i]])%MOD
        else:
            dp[i+1][ss] = dp[i][ss]*2 % 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 i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = (dp[i][ss]*2 % MOD + dp[i][ss-a[i]] % MOD)%MOD
        else:
            dp[i+1][ss] = dp[i][ss]*2 % 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 i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for ss in range(s+1):
        if(ss >= a[i]):
            dp[i+1][ss] = dp[i][ss]*2 % MOD + dp[i][ss-a[i]] % MOD
        else:
            dp[i+1][ss] = dp[i][ss]*2 % MOD

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

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] = (di[j]+2*dio[j])%mod
        for j in range(ai, s+1):
            di[j] = (di[j]+2*dio[j]+dio[j-ai])%mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()