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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, s = na()
a = na()

def invl(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p

mod = 98244353
i2 = invl(2, mod)
dp = [0] * (s+1)
dp[0] = pow(2, n, mod)

for x in a:
    for i in range(s, x-1, -1):
        dp[i] += dp[i-x] * i2
        dp[i] %= mod

print(dp[s] % mod)

Submission status: Wrong Answer

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, a in enumerate(A, start=1):
    for n in range(i)[::-1]:
        for s in range(S + 1):
            if s + a <= S:
                dp[n + 1][s + a] += dp[n][s]

ans = 0
for n in range(1, N + 1):
    mask = pow(2, N - n)
    ans += mask * dp[n][S]
print(ans)

Submission status: Time Limit Exceeded

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

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

    dp = [0]*(s+1)
    dp[0] = 1
    mod = 998244353

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

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

Submission status: Time Limit Exceeded

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

# ある数の取り得る状態は以下
# (1)部分集合Pに含まれない
# (2)部分集合Pに含まれ、和に使われている
# (3)部分集合Pに含まれ、和に使われていない

# dp[k] = 総和がkになっている場合の数
dp = [0] * (S + 1)
dp[0] = 1

for i in range(N):
  nextline = [0] * (S + 1)
  for k in range(S, -1, -1):
    # (1)部分集合Pに含まれない
    # (3)部分集合Pに含まれ、和に使われていない
    nextline[k] += dp[k] * 2
    nextline[k] %= DIV

    # (2)部分集合Pに含まれ、和に使われている
    if k + A[i] <= S:
      nextline[k + A[i]] += dp[k]
      nextline[k + A[i]] %= DIV
    
  dp = nextline

print(dp[-1])

Submission status: Time Limit Exceeded

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

# ある数の取り得る状態は以下
# (1)部分集合Pに含まれない
# (2)部分集合Pに含まれ、和に使われている
# (3)部分集合Pに含まれ、和に使われていない

# dp[j][k] = 部分集合Pに含まれ(j)、総和がkになっている場合の数
dp = [[0] * (S + 1) for j in range(2)]
dp[0][0] = 1

for i in range(N):
  nextline = [[0] * (S + 1) for j in range(2)]
  for k in range(S, -1, -1):
    # (1)部分集合Pに含まれない
    nextline[0][k] += dp[0][k]
    nextline[0][k] += dp[1][k]
    nextline[0][k] %= DIV

    # (2)部分集合Pに含まれ、和に使われている
    if k + A[i] <= S:
      nextline[1][k + A[i]] += dp[0][k]
      nextline[1][k + A[i]] += dp[1][k]
      nextline[1][k + A[i]] %= DIV

    # (3)部分集合Pに含まれ、和に使われていない
    nextline[1][k] += dp[0][k]
    nextline[1][k] += dp[1][k]
    nextline[1][k] %= DIV
    
  dp = nextline

print((dp[0][-1] + dp[1][-1]) % DIV)

Submission status: Time Limit Exceeded

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

# Sのそれぞれの項目について
# (1)Tに属さない
# (2)Tに属すが計算に使われない
# (3)Tに属して計算に使われる
# の3通りがある

# dp[i][j] = i番目の数を処理したときに、合計がjになるものは何通りあるか

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))

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

dp[0][0] = 1
for i in range(N):
  val = A[i]
  for j in range(len(dp[i]) - 1, -1, -1):
    if dp[i][j] == 0:
      continue
    dp[i + 1][j] += dp[i][j] * 2 # 使わない場合、選ばない場合
    dp[i + 1][j] %= DIV
    if j + val <= S:
      dp[i + 1][j + val] += dp[i][j]
      dp[i + 1][j + val] %= DIV
  
print(dp[-1][-1])

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 i in range(N)]
dp[0][0] = 2
if A[0] < S + 1:
	dp[0][A[0]] = 1

for i in range(1, N):
	for j in range(S + 1):
		dp[i][j] = (2 * dp[i - 1][j]) % MOD
		if 0 <= j - A[i] <= S:
			dp[i][j] = (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 = [-1 for _ in range(S+1)]
visited = [0]
dp[0] = 1
dp = tuple(dp)
for k in range(N):
  a = A[k]
  nextdp = list(dp)
  nextvisit = []
  for item in visited:
    #process1 追加する
    if item + a <= S:
      if nextdp[item+a] == -1:
        nextvisit.append(item+a)
        nextdp[item+a] = 0
      nextdp[item+a] += dp[item]
      nextdp[item+a] %= mod
    #process2 追加しない
    nextdp[item] += dp[item]
    nextdp[item] %= mod
  dp = tuple(nextdp)
  visited.extend(nextvisit)

print(max(dp[-1], 0))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc169/submissions/16260280
# F - Knapsack for All Subsets
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    res = 0
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            dp[i][j] %= mod
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]
            cnt_num[k] %= mod
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    """ 愚直解 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for prev in range(i):
            for j in range(s + 1):
                dp[i][j] += dp[prev][j]
                if a + j > s:
                    continue
                dp[i][a + j] += dp[prev][j]
                dp[i][a + j] %= mod
    print(dp)
    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


def resolve2():
    """ DP + 累積和 """
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cnt_num = [0] * (s + 1)
    cnt_num[0] = 1
    for i in range(1, n + 1):
        a = A[i - 1]
        for j in range(s + 1):
            dp[i][j] += cnt_num[j]
            if a + j > s:
                continue
            dp[i][a + j] += cnt_num[j]
            dp[i][a + j] %= mod
        for k in range(s + 1):
            cnt_num[k] = cnt_num[k] + dp[i][k]

    res = 0
    for i in range(1, n + 1):
        res += dp[i][-1]
        res %= mod
    print(res)


if __name__ == '__main__':
    n, s = map(int, input().split())
    A = list(map(int, input().split()))
    resolve2()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
conunter = [[0] for _ in range(S+1)] #counter[num][numに必要な要素数] = numの組み合わせ数
visited = [0]
conunter[0] = [1]

for k in range(N):
  a = A[k]
  new_count = []
  new_visit = []
  for item in visited:
    if item +a > S:
      continue
    if len(conunter[item+a]) == 1:
      new_visit.append(item+a)
    new_count.append((item + a, tuple(conunter[item])))
  visited.extend(new_visit)
  for new in new_count:
    for k in range(len(new[1])):
      plus = new[1][k]
      if len(conunter[new[0]]) < k+2:
        conunter[new[0]].append(plus)
      else:
        conunter[new[0]][k+1] += plus


two = [1]
for k in range(N):
  two.append(two[-1]*2%mod)


foo = conunter[-1]
ans = 0
for k in range(1, len(foo)): 
  ans = (ans + foo[k]*two[N-k])%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] * (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 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] = 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]] = dp[i+1][j+A[i]] % mod

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
import numpy
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    f = numpy.poly1d([1])
    zeros = [1 if x == 0 else 0 for x in range(3010)]
    for a in A:
        g = zeros[:a+1]
        g[-1] = 2
        f *= numpy.poly1d(g)
        
        h = [x % MOD for x in f]
        f = numpy.poly1d(h)


    print(f[S] % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD = 998244353

    f = numpy.poly1d([1])
    for a in A:
        g = [1 if x == 0 else 0 for x in range(a+1)]
        g[-1] = 2
        f *= numpy.poly1d(g)
        
        h = [x % MOD for x in f]
        f = numpy.poly1d(h)


    print(f[S] % MOD)



if __name__ == "__main__":
    main()

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(1,N+1):
    dp[i][0] = dp[i-1][0]*2%mod

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

ans = dp[-1][-1]%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod1,mod2=10**9+7,998244353
mod=mod2
n,s=map(int,input().split())
dp=[0]*(s+1)
dp[0]=1
for a in map(int,input().split()):
    for i in range(s,a-1,-1):
        dp[i]=(dp[i]*2%mod+dp[i-a])%mod
    for i in range(min(s,a-1),-1,-1):
        dp[i]=2*dp[i]%mod
        
print(dp[-1])

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

ans = 0
for i in range(1, n+1):
    ans = (ans + dp[i][s] * pow(2, n-i, mod)) % mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
# Tの部分集合をUとすると
# A[i]番目の項目について、
# (1)Tに選ばれない
# (2)Uに選ばれない
# (3)Uに選ばれる
# の3通りの遷移がある
# (1)(2)の場合も含めて数え上げていく（その場合、和は変わらない）

import sys
readline = sys.stdin.readline

N,S = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 998244353

dp = [0] * (S + 1)
dp[0] = 1
for i in range(N):
  newline = [0] * (S + 1)
  for j in range(len(dp)):
    # 選択肢(1)(2)の場合
    newline[j] += dp[j] * 2
    newline[j] %= DIV
    # 選択肢(3)の場合
    if j + A[i] <= S:
      newline[j + A[i]] += dp[j]
      newline[j + A[i]] %= DIV
  dp = newline

print(dp[S])

Submission status: Time Limit Exceeded

Solution code:
N, S=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[0]+A
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):
        dp[i][j]=(dp[i][j]+2*dp[i-1][j]) %998244353 # x[i]を入れないが、大きい方に入れるか入れないかが二通り
    for j in range(S-A[i]+1):
        dp[i][j+A[i]]=(dp[i][j+A[i]]+dp[i-1][j]) %998244353 # x[i]を入れる
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
N, S=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[0]+A
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):
        dp[i][j]=(dp[i][j]+2*dp[i-1][j]) %998244353 # x[i]を入れないが、大きい方に入れるか入れないかが二通り
        if j+A[i]<=S:
            dp[i][j+A[i]]=(dp[i][j+A[i]]+dp[i-1][j]) %998244353 # x[i]を入れる
print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
import  sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
mod=int(998244353)
#I=lambda: map(int,input().split())

n,m=map(int,input().split())
a=[int(x) for x in input().split()]
dp={}
def cal(n,s):
    if s<0:
        return 0
    if n<0:
        if s==0:
            return 1
        return 0
    if (n,s) in dp:
        return dp[(n,s)]
    r=cal(n-1,s)*2
    r+=cal(n-1,s-a[n])
    r%=mod
    dp[(n,s)]=r
    return r

ans=cal(n-1,m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# import numpy as np
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
# import bisect
# import math
import itertools
from collections import Counter
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


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



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# import numpy as np
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
# import bisect
# import math
import itertools
from collections import Counter
import numpy as np


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    l = [0, 1]
    ans = 0
    mod = 998244353
    for comb in itertools.product(l, repeat=N):
        if np.dot(comb, A) == S:
            ans += 2 **(N - sum(comb))
            ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

# Add dummy data at first position
A_list = [None] + list(map(int, input().rstrip().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):
        if (j - A_list[i+1]) >=0:
            dp[i+1][j] = dp[i][j - A_list[i+1]]
        
        dp[i+1][j] += 2*dp[i][j]
        dp[i+1][j] %= mod

print(dp[N][S])

Submission status: Time Limit Exceeded

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

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

# Add dummy data at first position
A_list = [None] + list(map(int, input().rstrip().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):
        if (j - A_list[i+1]) >=0:
            dp[i+1][j] = 2*dp[i][j] + dp[i][j - A_list[i+1]]
        else:
            dp[i+1][j] = 2*dp[i][j]
        
        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()))
combi = [[0]*(s+1) for i in range(n)]
combi[0][0] = 2
if a[0] <= s:
  combi[0][a[0]] = 1
mod = 998244353
for i in range(1, n):
  for j in range(s+1):
      combi[i][j] += combi[i-1][j] * 2
      combi[i][j] %= 998244353
      if j + a[i] <= s:
        combi[i][j+a[i]] += combi[i-1][j]
        combi[i][j+a[i]] %= 998244353
print(combi[n-1][s])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
P=998244353
A = [0]+list(map(int,input().split()))
dp = [[0]*(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):
		dp[i][j] = (dp[i][j] + 2*dp[i-1][j])%P
		if A[i]+j<=S:
			dp[i][A[i]+j] = dp[i][A[i]+j] + dp[i-1][j]
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 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:
def main():
    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(1, n+1):
        ai = a[i-1]
        for j in range(s+1):
            dp[i][j] += dp[i-1][j]*2
            if j >= ai:
                dp[i][j] += dp[i-1][j-ai]
            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()))
P = 998244353
table = [[0 for _ in range(S+1)] for _ in range(N)]
table[0][0] = 2
if A[0]<=S:
    table[0][A[0]] = 1
for i in range(1, N):
    Ai = A[i]
    for j in range(S+1):
        table[i][j] += (2*table[i-1][j])
        if j+Ai<=S:
            table[i][j+Ai] += table[i-1][j] 

print(table[N-1][S]%P)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import math
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter

n,s=map(int,readline().split())
a=list(map(int,readline().split()))
mod=998244353
dp=np.zeros((3030,3030),np.int64)
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 = 998_244_353

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

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

b = 1
k = 2
modpow_t = [1]
for _ in range(1,N+1):
  b = (b*k)%MOD
  modpow_t.append( b )
#

ans = 0

def DFS(n, m, t):
  global ans
  if t > S:
    return
  if t == S:
    ans = (ans+modpow_t[N-m])%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:
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)
dp[0] = 1

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

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):
        here = dp[i][j]
        # aiがTに含まれない
        dp[i + 1][j] += here
        # aiがTに含まれるが, Uに含まれない
        dp[i + 1][j] += here

        dp[i + 1][j] %= MOD

        # aiがUに含まれる
        if j + ai <= S:
            dp[i + 1][j + ai] += dp[i][j]
            dp[i + 1][j + ai] %= MOD

print(dp[N][S])

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
#dp[i][j]:集合{A[k]|k=0,1,,,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] #A[i]を使わない場合、集合{A[k]|k=0,1,,,i}の部分集合の数が2倍だけ増える
        dp[i+1][j] %= mod
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j] #A[i]を使う場合、総和が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 = [int(a) for a in input().split()]
mod = 998244353

A.sort()
num = 0
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    num += A[i]
    for j in range(i+1, 0, -1):
        for k in range(A[i], min(num, S)+1):
            dp[j][k] += dp[j-1][k-A[i]]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
P = 998244353

# N = 10
# S = 10
# AS = list(map(int, "3 1 4 1 5 9 2 6 5 3".split()))
N, S = map(int, input().split())
AS = list(map(int, input().split()))
DP = np.zeros((S + 1, N + 1), dtype=np.int64)
DP[0, 0] = 1
# print(DP)

for i in range(N):
    for j in range(S + 1):
        v = DP[j, i] * 2
        if AS[i] <= j:
            v += DP[j - AS[i], i]
        DP[j, i + 1] = v % P

# print(DP)
print(DP[S, N])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
DP = [[0] * (1 + S) for _ in range(1 + N)]  # DP[i][j] はi番目までみた時に総和がjと成る組み合わせの総和
# 初期化
DP[0][0] = 1
# 漸化式　DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-A[i]]
for i in range(1, N + 1):
    for j in range(S + 1):
        if j >= A[i - 1]:
            DP[i][j] = DP[i - 1][j] * 2 + DP[i - 1][j - A[i - 1]]
        else:
            DP[i][j] = DP[i - 1][j] * 2
        DP[i][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()))
var1 = [0] * (S + 1)
var1[0] = pow(2, N, 998244353)
var2 = pow(2, 998244353 - 2, 998244353)
m = 0
for all in A:
    m = all+m
    funcvar1=min(S, m)
    for val in reversed(range(all,funcvar1+1)):
        var1[val] = (var1[val] + var1[val - all] * var2) % 998244353
ans=var1[S]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
m = 0
var1 = [0] * (S + 1)
var1[0] = pow(2, N, 998244353)
var2 = pow(2, 998244353 - 2, 998244353)
for all in A:
    m = all+m
    funcvar1=min(S, m)
    for val in reversed(range(all,funcvar1+1)):
        var1[val] = (var1[val] + var1[val - all] * var2) % 998244353
print(var1[S])

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
m = 0
var1 = [0] * (S + 1)
var1[0] = pow(2, N, 998244353)
var2 = pow(2, 998244353 - 2, 998244353)
def func1(xxx, xx):
    if xxx>xx:
        return xx
    else:
        return xxx
for all in A:
    m = all+m
    funcvar1=func1(S, m)
    for val in reversed(range(all,funcvar1+1)):
        var1[val] = (var1[val] + var1[val - all] * var2) % 998244353
print(var1[S])

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split()) 
a=list(map(int,input().split()))
mod=998244353
d=[[0 for l in range(s+1)] for _ in range(n+1)]
d[0][0]=1
for i in range(1,n+1):
    val=a[i-1]
    for j in range(0,s+1):
        d[i][j]+=2*d[i-1][j]
        d[i][j]%=mod
        if val<=j:
            d[i][j]+=d[i-1][j-val]
            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()))
d=[[0]*(s+1) for _ in range(n+1)]
d[0][0]=1
for j in range(0,s+1):
    for i in range(1,n+1):
        d[i][j]=2*d[i-1][j]
        if a[i-1]<=j:
            d[i][j]+=d[i-1][j-a[i-1]]
        d[i][j]=d[i][j]%998244353
print(d[n][s])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = [int(i) for i in input().split()]
    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for i in a:
        p = np.zeros(s + 1, dtype="int32")
        dp, p = p, dp
        dp += (p * 2) % MOD
        dp %= MOD
        for j in range(s + 1):
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
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):
    a=A[i-1]
    for j in range(0,S+1):
        dp[i][j]+=dp[i-1][j]*2
        if j-a>=0:
            dp[i][j]+=dp[i-1][j-a]
        dp[i][j]=dp[i][j]%MOD


print(dp[N][S])

Submission status: Time Limit Exceeded

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

print(DP[N][S])

Submission status: Time Limit Exceeded

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

print(DP[N][S])

Submission status: Time Limit Exceeded

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

print(DP[N][S])

Submission status: Time Limit Exceeded

Solution code:
import itertools
p = 998244353
q = 75497471

N,S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
L = []
for i in range(1,N+1):
  for a in itertools.combinations(range(N),i):
    num = 0
    for j in a:
      num += A[j]
    if num == S:
      L.append(i)
ans = 0
for l in L:
  l = N-l
  t = l//30
  u = l%30
  num = 1
  for _ in range(t):
    num *= q
    num %= p
  num *= 2**u
  num %= p
  ans += num
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    a = np.array([int(i) for i in input().split()], dtype="int16")
    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for i in a:
        p = np.zeros(s + 1, dtype="int32")
        dp, p = p, dp
        dp += p * 2
        dp %= MOD
        for j in range(s + 1):
            # print(f"{i = }, {j = }, {dp = }, {p = }")
            if (ji := j + i) <= s:
                dp[ji] = (dp[ji] + p[j]) % MOD

    print(dp[s])


if __name__ == '__main__':
    main()