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
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(S+1,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = dp*2
    if a > S:
        continue
    else:
        p[a:] += dp[:S-a+1]
        dp = p % MOD
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
import numpy as np
N,S = map(int,input().split())
MOD = 998244353
A = list(map(int,input().split()))
dp = np.zeros(S+1,dtype = np.int64)
dp[0] = 2
if A[0] <= S:
    dp[A[0]] = 1
for i in range(1,N):
    a = A[i]
    p = (dp*2)%MOD
    if a > S:
        continue
    else:
        p[a:] += dp[:S-a+1]
        dp = p % MOD
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]

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

Submission status: Wrong Answer

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])

Submission status: Wrong Answer

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 に加えない場合
        dp[i+1] += dp[i]*2  # T に加える／加えない
        for j in range(S+1):
            # 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: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,copy
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,s = inpl()
a = inpl()
dp = [[0]*(s+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j] * 2
        if j - a[i] >= 0:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= mod
# print(dp)
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys


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)
            else:
                dp[i][j] = dp[i - 1][j] * 2
    print(dp[n][s])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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, j - var] != 0:
            dp[i, j] += dp[i - 1, j - var]
            dp[i, j] %= mod
print(int(dp[n, s]))

Submission status: Wrong Answer

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(dp)
print(int(dp[n, s]))

Submission status: Wrong Answer

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

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

for i in range(n):
    plus = [dp[j-a[i]]  if j-a[i] >=0 else 0 for j in range(s+1)]
    for j in range(s+1):
        dp[j] = dp[j]*2 +plus[j]

print(dp[s])

Submission status: Wrong Answer

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

dp = np.array([0 for _ in range(s+1)])
dp[0] = 1

for i in range(n):
    plus = [dp[j-a[i]]  if j-a[i] >=0 else 0 for j in range(s+1)]
    dp = dp*2
    dp = dp+plus

print(dp[s])

Submission status: Wrong Answer

Solution code:
def f_knapsack_for_all_subsets_power_series(MOD=998244353, MAX=3010):
    # 参考: https://maspypy.com/atcoder-参加感想-2020-05-31abc-169
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    f = np.zeros(MAX + 1, np.int64)  # 次数が S より大きな項には興味ないため、こうする
    f[0] = 1  # f_{0}(x) = 1
    for a in A:
        # f_{n+1} = f_{n} * (2 + x**a) = 2 * f_{n} + x**a * f_{n}
        f_next = 2 * f  # 第一項
        f_next[a:] += f[:-a]  # 第二項
        f_next % MOD
        f = f_next
    return f[S]

print(f_knapsack_for_all_subsets_power_series())

Submission status: Wrong Answer

Solution code:
def f_knapsack_for_all_subsets_power_series(MOD=998244353, MAX=3000):
    # 参考: https://maspypy.com/atcoder-参加感想-2020-05-31abc-169
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    f = np.zeros(MAX + 1, np.int64)  # 次数が S より大きな項には興味ないため、こうする
    f[0] = 1  # f_{0}(x) = 1
    for a in A:
        # f_{n+1} = f_{n} * (2 + x**a) = 2 * f_{n} + x**a * f_{n}
        f_next = 2 * f  # 第一項
        f_next[a:] += f[:-a]  # 第二項
        f_next % MOD
        f = f_next
    return f[S]

print(f_knapsack_for_all_subsets_power_series())

Submission status: Wrong Answer

Solution code:
def f_knapsack_for_all_subsets_power_series(MOD=998244353):
    # 参考: https://maspypy.com/atcoder-参加感想-2020-05-31abc-169
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    f = np.zeros(S + 1, np.int64)  # 次数が S より大きな項に興味ない
    f[0] = 1  # f_{0}(x) = 1
    for a in A:
        # f_{n+1} = f_{n} * (2 + x**a) = 2 * f_{n} + x**a * f_{n}
        f_next = 2 * f  # 第一項
        f_next[a:] += f[:-a]  # 第二項
        f_next % MOD
        f = f_next
    return f[S]

print(f_knapsack_for_all_subsets_power_series())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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] += 1
      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: Wrong Answer

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1000)
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod


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

    dpt = [dict() for i in range(S+1)]

    dpt[0][0] =1
    mx = 0
    for i in A:
        for j in range(min(mx,S-i)+1,-1,-1):
            if dpt[j]:
                mx = max(j+i,mx)
            if i+j > S:
                continue 
            for k in dpt[j]:
                if not k+1 in dpt[j+i]:
                    dpt[j+i][k+1]=0
                dpt[j+i][k+1]+=dpt[j][k]
    ans = 0
    for i in dpt[-1]:
        ans += (pow_r(2,N-i,mod=998244353)*dpt[-1][i])%998244353
    print(ans)
resolve()

Submission status: Wrong Answer

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

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]]
        else:
            dp[i+1][ss] = dp[i][ss]*2

print(dp[n][s])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod = 998244353

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

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

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

print(dp[N][S])

Submission status: Wrong Answer

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

    for n in range(1, N):
        dp *= 2
        dp[An[n]:] += dp[:-An[n]] // 2

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = [[0] * (S + 1) for _ in range(2)]
    dp[0][0] = 2
    if An[0] <= S:
        dp[0][An[0]] = 1
    for n in range(1, N):
        dp[(n)%2] = [0] * (S + 1)
        for k in range(S + 1):
            for j in range(2):
                if j:
                    dp[n%2][k] += dp[(n-1)%2][k] * 2
                else:
                    if k + An[n] > S:
                        continue
                    dp[n%2][k+An[n]] += dp[(n-1)%2][k]

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    N, S = [int(x) for x in input().strip().split()]
    An = [int(x) for x in input().strip().split()]
    dp = [[0] * (S + 1) for _ in range(N)]
    dp[0][0] = 2
    if An[0] <= S:
        dp[0][An[0]] = 1
    for n in range(1, N):
        for k in range(S + 1):
            for j in range(2):
                if j:
                    dp[n][k] += 2 * dp[n-1][k]
                else:
                    if k + An[n] > S:
                        continue
                    dp[n][k+An[n]] += dp[n-1][k]
    
    # for d in dp:
        # print(d)
    print(dp[N-1][S])
                
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 998244353
INF = float('inf')


N, A = MI()
a = [0, *list(map(int, input().split()))]

# dp[i][j] := i番目までの数字を使って総和をjとする場合の数
# dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j]
dp = [[0] * (A + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(A + 1):
        if j - a[i] < 0:  # j - a[i] が負の数になってしまう時はa[i]を使用することはできない
            dp[i][j] = 2 * dp[i - 1][j]
            continue
        dp[i][j] = (dp[i - 1][j - a[i]] + 2 * dp[i - 1][j]) % MOD
print(dp[N][A])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))
U = 3001
fft_len = 1 << U.bit_length()

X = np.zeros(U, dtype=np.int64)
X[0] = 1

for a in A:
    F = np.zeros_like(X)
    F[0] = 2
    F[a] = 1
    X = (ifft(fft(X, fft_len) * fft(F, fft_len), fft_len) + 0.5).astype(np.int64)
    X %= mod

print(X[S])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

mod = 998244353

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

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

#print(DP)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import math 
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def read():
  return float(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
dp=[{0:1} for i  in range(n)]
for i in range(n):
    for j in sorted(list(dp[i]))[::-1]:
        if i<n-1:
          dp[i+1]=dp[i].copy()
        try:
            dp[i][a[i]+j]+=dp[i][j]
        except:
            dp[i][a[i]+j]=dp[i][j]
        if i<n-1:
          try:
              dp[i+1][a[i]+j]+=dp[i][j]
              if dp[i+1][a[i]+j]>s:
                dp[i+1].pop(a[i]+j)
          except:
              dp[i+1][a[i]+j]=dp[i][j]      
    #dp[i+1]=dp[i]
print(dp)

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
import math 
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def read():
  return float(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod=[[] for _ in range(n)]
dp=[{0:1} for i  in range(n)]
for i in range(n):
    for j in list(dp[i] ):
        dp[i][a[i]+j]=dp[i][j]
    if i==n-1:
      break
    dp[i+1]=dp[i]
print(dp)

Submission status: Wrong Answer

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

mod = 998244353

pows = [1]
for i in range(10000):
    pows.append((pows[-1] * 2) % mod)

dp = [0] * (s + 1)
dp[0] = 1
if a[0] <= s:
    dp[a[0]] = 1

for i in range(1, n):
    dp_new = [0] * (s + 1)
    dp_new[0] = 1
    for j in range(1, s + 1):
        dp_new[j] = dp[j] * 2

        if j - a[i-1] > 0:
            dp_new[j] += dp[j-a[i-1]]
        elif j == a[i-1]:
            dp_new[j] += pows[i]
        dp_new[j] %= mod

    dp = dp_new

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mod = 998244353

pows = [1]
for i in range(10000):
    pows.append((pows[-1] * 2) % mod)

dp = [[0] * 3001 for _ in range(n)]
dp[0][a[0]] = 1
for i in range(n):
    dp[i][0] = 1


for i in range(1, n):
    for j in range(1, 3001):
        dp[i][j] = dp[i-1][j] * 2

        if j - a[i-1] > 0:
            dp[i][j] += dp[i-1][j-a[i-1]]
        elif j == a[i-1]:
            dp[i][j] += 2 ** i
        dp[i][j] %= mod

print(dp[-1][s])

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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

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


print(dp[n][s])

Submission status: Wrong Answer

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

MOD=998244353

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

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

Submission status: Wrong Answer

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

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

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

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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, dtype=int)
dp[0] = 1

for i in A:
    ep = dp.copy()
    ep += dp
    ep[i:] += dp[:-i]
    dp = ep

print(dp[S])

Submission status: Wrong Answer

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]

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

Submission status: Wrong Answer

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][j] %= MOD
print(dp[n][s])

Submission status: Wrong Answer

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
ma = 10**7
inf = float("inf")
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][j] %= MOD
print(dp[n][s])

Submission status: Wrong Answer

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

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
    if j-a >= 0:
      dp[i][j] += dp[i-1][j-a]
      
print(dp[N][S])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
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] = 2**n
    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]]//2
            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: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
mod = 998244353
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] = 2**n
    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]]//2
        for j in range(s,-1,-1):
                dp[i+1][j] += dp[i][j]
    print(dp[n][s])
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
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]
    if j >=A[i]:
      dp[i+1][j] += dp[i][j-A[i]]
print(dp[N][S])

Submission status: Wrong Answer

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

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(1)
    exit()

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

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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] = 1

for i in range(1, N+1):
  for j in range(S+1):
    if j - A[i-1] < 0:
      DP[i][j] = 2 * DP[i-1][j]
    else:
      DP[i][j] = DP[i-1][j-A[i-1]] + 2 * DP[i-1][j]
    
ans = DP[N][S]
print(ans)

#print(DP)