Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
import copy
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる集合のサイズのリスト
    DP = [None]*(S+1)
    DP[0] = [0]
    DP_new = copy.deepcopy(DP)
    for i in range(1, N+1):
        for wa in range(S+1):
            if 0 <= wa-A[i-1] <= S:
                if DP[wa-A[i-1]] is not None:
                    if DP_new[wa] is None:
                        DP_new[wa] = [(k+1) % MOD for k in DP[wa-A[i-1]]]
                    else:
                        DP_new[wa] += [(k+1) % MOD for k in DP[wa-A[i-1]]]
        DP = copy.deepcopy(DP_new)
        # print(DP)

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる
    ans = 0
    if DP[-1] is None:
        print(0)
        return
    for s in DP[-1]:
        ans += pow(2, N - s, MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のサイズのリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                ans.append(1)
            else:
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb+1 for bb in b])
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - s, MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    # DP = [[0]*(S+1) for i in range(N+1)]
    # DP[0][0] = 1
    # for i in range(1, N+1):
    #     DP[i][0] = 1
    #     for wa in range(S+1):
    #         DP[i][wa] = DP[i-1][wa]
    #         if 0 <= wa-A[i-1] <= S:
    #             DP[i][wa] += DP[i-1][wa-A[i-1]]
    #             DP[i][wa] %= MOD
    DP = [0]*(S+1)
    DP[0] = 1
    DP_new = DP[:]
    for i in range(N):
        for wa in range(S+1):
            if 0 <= wa-A[i] <= S:
                DP_new[wa] += DP[wa-A[i]]
                DP_new[wa] %= MOD
        DP = DP_new

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    # DP = [[0]*(S+1) for i in range(N+1)]
    # DP[0][0] = 1
    # for i in range(1, N+1):
    #     DP[i][0] = 1
    #     for wa in range(S+1):
    #         DP[i][wa] = DP[i-1][wa]
    #         if 0 <= wa-A[i-1] <= S:
    #             DP[i][wa] += DP[i-1][wa-A[i-1]]
    #             DP[i][wa] %= MOD
    DP = [0]*(S+1)
    DP[0] = 1
    DP_new = DP[:]
    for i in range(N):
        for wa in range(S+1):
            if 0 <= wa-A[i] <= S:
                DP_new[wa] += DP[wa-A[i]]
                DP_new[wa] %= MOD
        DP = DP_new

    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
                DP[i][wa] %= MOD
    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        if n-1 >= 0 and DP[n-1][wa] != 0:
            ans.extend(reconstruct(n-1, wa))
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                if n-1 >= 0 and DP[n-1][wa-A[n-1]] != 0:
                    b = reconstruct(n-1, wa-A[n-1])
                    ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        ans += pow(2, N - len(s), MOD)
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  # type: int


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

    # 和がSとなるように選択する
    # DP[i][wa] ... i文字目まで見て和がwaとなる個数
    DP = [[0]*(S+1) for i in range(N+1)]
    DP[0][0] = 1
    for i in range(1, N+1):
        DP[i][0] = 1
        for wa in range(S+1):
            DP[i][wa] = DP[i-1][wa]
            if 0 <= wa-A[i-1] <= S:
                DP[i][wa] += DP[i-1][wa-A[i-1]]
    # print(*DP, sep="\n")

    # 組み合わせはDP[N][S]個存在する。
    # DPを逆に辿って集合を得る
    # 集合を含むような部分集合を数えあげる

    @lru_cache(maxsize=None)
    def reconstruct(n, wa):
        # nまで見て、和がwaとなるような集合のリストを返す
        # print("(n, wa)", n, wa)
        ans = []
        if wa < 0 or n < 0 or DP[n][wa] == 0:
            # print("?")
            return ans
        ans += reconstruct(n-1, wa)
        if DP[n][wa] != DP[n-1][wa]:
            # 文字の追加がある
            if wa-A[n-1] == 0:
                # print("only")
                ans.append({n-1})
            else:
                # print("add")
                b = reconstruct(n-1, wa-A[n-1])
                ans.extend([bb | {n-1} for bb in b])
        # print("ret, ", ans)
        return ans

    ans = 0
    for s in reconstruct(N, S):
        # print(s)
        # print(s, [A[i] for i in s])
        ans += pow(2, N - len(s), MOD)
        # print(2**(N - len(s)))
        ans %= MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**8)

MOD = 998244353  # type: int


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

    print(DP[N][S])
    return


if __name__ == '__main__':
    main()