Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353
MAX = 3010


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


INV = [1] * (MAX+1)
INV[MAX] = div(1, pow(2, MAX, MOD))
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * 2) % MOD


def encode(num, total, S):
    return num * (S+1) + total


def decode(val, S):
    return val // (S+1), val % (S+1)


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * div(1, 2)) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()


Fixed submission:
MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353


def encode(num, total, S):
    return num * (S+1) + total


def decode(val, S):
    return val // (S+1), val % (S+1)


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split()), reverse=True))
    prev = {encode(0, 0, S): 1}
    for i in range(N):
        cur = {k: prev[k] for k in prev}
        for prevkey in prev:
            num, total = decode(prevkey, S)
            if total + A[i] > S:
                continue
            key = encode(num+1, total + A[i], S)
            if key in cur:
                cur[key] = cur[key] + prev[prevkey]
            else:
                cur[key] = prev[prevkey]
        prev = cur
    ans = 0
    for num in range(1, N+1):
        key = encode(num, S, S)
        if key in cur:
            ans = (ans + cur[key] * pow(2, N-num, MOD)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = {(0, 0): 1}
    for i in range(N):
        cur = {k: prev[k] for k in prev}
        for num, total in prev:
            if total + A[i] > S:
                continue
            key = (num+1, total + A[i])
            if key in cur:
                cur[key] = cur[key] + prev[(num, total)]
            else:
                cur[key] = prev[(num, total)]
        prev = cur
    ans = 0
    for num in range(1, N+1):
        if (num, S) in cur:
            ans = (ans + cur[(num, S)] * pow(2, N-num, MOD)) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(sorted(map(int, input().split())))
    prev = [0] * (S+1)
    prev[0] = pow(2, N, MOD)
    half = pow(2, MOD-2, MOD) % MOD
    for i in range(N):
        cur = list(prev)
        for total in range(S+1):
            if total + A[i] > S:
                continue
#            key = encode(num+1, total + A[i], S)
            cur[total + A[i]] = (cur[total + A[i]] +
                                 prev[total] * half) % MOD
        prev = cur
    print(cur[S])


if __name__ == "__main__":
    main()