Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = map(int, input().split())

B_C = B // C
B_D = B // D
B_C_D = B // lcm(C, D)

A_C = (A - 1) // C
A_D = (A - 1) // D
A_C_D = (A - 1) // lcm(C, D)

B_div = B_C + B_D - B_C_D
A_div = A_C + A_D - A_C_D



print(B - A + 1 - (B_div - A_div))


Fixed submission:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A, B, C, D = map(int, input().split())

B_C = B // C
B_D = B // D
B_C_D = B // lcm(C, D)

A_C = (A - 1) // C
A_D = (A - 1) // D
A_C_D = (A - 1) // lcm(C, D)

B_div = B_C + B_D - B_C_D
A_div = A_C + A_D - A_C_D



print(B - A + 1 - (B_div - A_div))
Buggy python submission (verdict: Runtime Error):
N = int(input())

l = []
for _ in range(N) :
    ll = list(map(int, input().split()))
    l.append(ll)

#print(l)

dic = {}

for i in range(1, N) :
    #subl.append([l[i][0] - l[i-1][0], l[i][1] - l[i-1][1]])
    #k = 1000000001*(l[i][0] - l[i-1][0]) + l[i][1] - l[i-1][1]
    k = str(l[i][0] - l[i-1][0]) + '+' + str(l[i][1] - l[i-1][1])

    if l[i][0] - l[i-1][0] == 0 and l[i][1] - l[i-1][1] == 0:
        continue

    if k not in dic :
        dic[k] = 1
    else :
        dic[k] += 1

print(dic)

if len(dic) == 0 :
    print(N)
else :
    print(N - max(dic.values()))


Fixed submission:
N, K = map(int, input().split())
if K == 1 :
    print(0)
else :
    print(N-K)
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N//R + 1) :
    for j in range(N//G + 1) :
        if N - R*i - G*j >= 0 :
            if (N - R*i - G*j) % B == 0:
                cnt += 1

print(cnt)


Fixed submission:
R, G, B, N = map(int, input().split())

cnt = 0

for i in range(N//R + 1) :
    for j in range((N - R*i)//G + 1) :
        if (N - R*i - G*j) % B == 0:
            cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = input()
K = int(input())

a = S[K + 1]

for i in range(len(S)) :
    if S[i] != a :
        print('*', end="")
    else :
        print(S[i], end="")
print()


Fixed submission:
N = int(input())
S = input()
K = int(input())

a = S[K - 1]

for i in range(len(S)) :
    if S[i] != a :
        print('*', end="")
    else :
        print(S[i], end="")
print()
Buggy python submission (verdict: Time Limit Exceeded):
import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

array = []

for m in re.finditer(r'AC', S):
    array.append(m.start())


for i in range(Q) :
    count = 0
    for j in range(len(array)) :
        if L[i][0] - 1 <= array[j] and L[i][1] - 2 >= array[j] :
            count += 1
    print(count)


Fixed submission:
import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

array = [0 for i in range(N + 1)]
for i in range(N) :
    array[i + 1] = array[i] + (1 if S[i: i + 2] == 'AC' else 0)

for i in range(Q) :
    print(array[L[i][1] - 1] - array[L[i][0] - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

for i in range(Q) :
    subStr = S[L[i][0] - 1:L[i][1]]
    print(subStr.count('AC'))


Fixed submission:
import re

N, Q = map(int, input().split())
S = input()
L = [list(map(int, input().split())) for i in range(Q)]

array = [0 for i in range(N + 1)]
for i in range(N) :
    array[i + 1] = array[i] + (1 if S[i: i + 2] == 'AC' else 0)

for i in range(Q) :
    print(array[L[i][1] - 1] - array[L[i][0] - 1])
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int, input().split())
print(min(-(-B//A), C)

Fixed submission:
A, B, C = map(int, input().split())

if (B / A < C) :
    print(B // A)
else :
    print(C)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()

count = 0

while True :
    length = len(S)
    S = S.replace("01", "")
    S = S.replace("10", "")
    if (length == len(S)) :
        break
    count += length - len(S)
print(count)

Fixed submission:
S = input()

count = 0
index = -1

print(2 * min(S.count("0"), S.count("1")))
Buggy python submission (verdict: Runtime Error):
sum = 0

num = int(input())

if num < 1 or num > 10 :
    return
    
for i in range(num) :
    money, currency = input().split()
    money = double(money)
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)

Fixed submission:
sum = 0

num = int(input())

for i in range(num) :
    money, currency = input().split()
    money = float(money)
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)

Buggy python submission (verdict: Runtime Error):
sum = 0

num = int(input())

for i in range(num) :
    money, currency = input().split()
    money = int(money)
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)

Fixed submission:
sum = 0

num = int(input())

for i in range(num) :
    money, currency = input().split()
    money = float(money)
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)

Buggy python submission (verdict: Runtime Error):
sum = 0

num = int(input())

for i in range(num) :
    money = int(input())
    currency = input()
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)

Fixed submission:
sum = 0

num = int(input())

for i in range(num) :
    money, currency = input().split()
    money = float(money)
    if currency == 'JPY' :
        sum += money
    else :
        sum += money * 380000

print(sum)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

l = [['P' for _ in range(H + 2)] for _ in range(W + 2)]

for i in range(H) :
    s = list(input())
    for j in range(W) :
        l[i+1][j+1] = s[j]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ans = True

for i in range(1, H + 1) :
    for j in range(1, W + 1) :
        if l[i][j] != "#" :
            continue
        flag = False
        for k in range(len(dx)) :
            if l[i + dx[k]][j + dy[k]] == "#" :
                flag = True
                break
        if flag == False :
            ans = False

if ans :
    print('Yes')
else :
    print('No')


Fixed submission:
H, W = map(int, input().split())

l = [['P' for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H) :
    s = list(input())
    for j in range(W) :
        l[i+1][j+1] = s[j]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ans = True

for i in range(1, H + 1) :
    for j in range(1, W + 1) :
        if l[i][j] != "#" :
            continue
        flag = False
        for k in range(len(dx)) :
            if l[i + dx[k]][j + dy[k]] == "#" :
                flag = True
                break
        if flag == False :
            ans = False

if ans :
    print('Yes')
else :
    print('No')

Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

l = [['P' for _ in range(H + 2)] for _ in range(W + 2)]

for i in range(H) :
    s = list(input())
    for j in range(W) :
        l[i+1][j+1] = s[j]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ans = True

for i in range(1, H + 1) :
    for j in range(1, W + 1) :
        if l[i][j] != "#" :
            continue
        flag = False
        for k in range(len(dx)) :
            if l[i + dx[k]][j + dy[k]] == "#" :
                flag = True
                break
        if flag == False :
            ans = False

if ans :
    print('Yes')
else :
    print('No')


Fixed submission:
H, W = map(int, input().split())

l = [['P' for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H) :
    s = list(input())
    for j in range(W) :
        l[i+1][j+1] = s[j]

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ans = True

for i in range(1, H + 1) :
    for j in range(1, W + 1) :
        if l[i][j] != "#" :
            continue
        flag = False
        for k in range(len(dx)) :
            if l[i + dx[k]][j + dy[k]] == "#" :
                flag = True
                break
        if flag == False :
            ans = False

if ans :
    print('Yes')
else :
    print('No')
Buggy python submission (verdict: Runtime Error):
c = [list(map(int, input().split())) for i in range(3) ]

ans = False

for i in range(max(101)) :
    a1 = 0
    b1 = c[0][0]
    b2 = c[0][1]
    b3 = c[0][2]
    a2 = c[1][0] - b1
    a3 = c[2][0] - b1
    a = []
    a.append(a1)
    a.append(a2)
    a.append(a3)
    if a2 + b2 != c[1][1] :
        continue
    elif a3 + b2 != c[2][1] :
        continue
    elif a2 + b3 != c[1][2] :
        continue
    elif a3 + b3 != c[2][2] :
        continue
    ans = True
    break

if ans :
    print('Yes')
else :
    print('No')


Fixed submission:
c = [list(map(int, input().split())) for i in range(3) ]

ans = False

for i in range(101) :
    for j in range(101) :
        for k in range(101) :
            b1 = c[0][0] - i
            b2 = c[1][0] - i
            b3 = c[2][0] - i
            if j + b1 != c[0][1] :
                continue
            elif j + b2 != c[1][1] :
                continue
            elif j + b3 != c[2][1] :
                continue
            elif k + b1 != c[0][2] :
                continue
            elif k + b2 != c[1][2] :
                continue
            elif k + b3 != c[2][2] :
                continue
            ans = True

if ans :
    print('Yes')
else :
    print('No')

Buggy python submission (verdict: Runtime Error):
c = [list(map(int, input().split())) for i in range(3) ]

ans = False

for i in range(max(c)) :
    a1 = 0
    b1 = c[0][0]
    b2 = c[0][1]
    b3 = c[0][2]
    a2 = c[1][0] - b1
    a3 = c[2][0] - b1
    a = []
    a.append(a1)
    a.append(a2)
    a.append(a3)
    if a2 + b2 != c[1][1] :
        continue
    elif a3 + b2 != c[2][1] :
        continue
    elif a2 + b3 != c[1][2] :
        continue
    elif a3 + b3 != c[2][2] :
        continue
    ans = True
    break

if ans :
    print('Yes')
else :
    print('No')


Fixed submission:
c = [list(map(int, input().split())) for i in range(3) ]

ans = False

for i in range(101) :
    for j in range(101) :
        for k in range(101) :
            b1 = c[0][0] - i
            b2 = c[1][0] - i
            b3 = c[2][0] - i
            if j + b1 != c[0][1] :
                continue
            elif j + b2 != c[1][1] :
                continue
            elif j + b3 != c[2][1] :
                continue
            elif k + b1 != c[0][2] :
                continue
            elif k + b2 != c[1][2] :
                continue
            elif k + b3 != c[2][2] :
                continue
            ans = True

if ans :
    print('Yes')
else :
    print('No')
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

count = 0
while sum(list(map(lambda x: x % 2, A))) == 0 :
    count += 1
    A = list(map(lambda x: x / 2, A))

print(count)


Fixed submission:
print(input().count('1'))
Buggy python submission (verdict: Runtime Error):
n = int(input())
for i in range(7) :
    if (2**i) < n :
        ans = 2**i
print(ans)


Fixed submission:
N = int(input())

nList = [i + 1 for i in range(N)]
res = -1
counter = -1
for n in nList :
    count = 0
    buf = n
    while buf % 2 == 0 :
        count += 1
        buf = buf / 2
    if counter < count :
        counter  = count
        res = n
print(res)

Buggy python submission (verdict: Runtime Error):
n = int(input())
for i in range(1, 7) :
    if (2**i) < n :
        ans = 2**i
print(ans)


Fixed submission:
N = int(input())

nList = [i + 1 for i in range(N)]
res = -1
counter = -1
for n in nList :
    count = 0
    buf = n
    while buf % 2 == 0 :
        count += 1
        buf = buf / 2
    if counter < count :
        counter  = count
        res = n
print(res)
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n, k;
  cin >> n >> k;
  int l[k];
  rep(i, n) cin >> l[i];

  sort(l, l+n, greater<int>());
  int sum = 0;
  rep(i, k) sum += l[i];

  cout << sum << endl;

}


Fixed submission:
N, K = map(int, input().split())
l= list(map(int, input().split()))

l.sort(reverse = True)
sum = 0
for i in range(K) :
    sum += l[i]
print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = []
for i in range(N) :
    a.append(int(input()))

index = 1
cnt = 0

while True:
    index = a[index - 1]
    cnt += 1
    if index == 2 :
        break
    if index == 1 :
        cnt = -1
        break

print(cnt)


Fixed submission:
N = int(input())
a = []
for i in range(N) :
    a.append(int(input()))

index = 1
cnt = 0

for i in range(N):
    index = a[index - 1]
    cnt += 1
    if index == 2 :
        break
    if index == 1 :
        cnt = -1
        break
    if i == N - 1 :
        cnt = -1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

sum = a[0]
count = 0

for i in range(1, n) :
    temp = sum
    sum += a[i]
    if temp > 0 and sum > 0 :
        while sum >= 0 :
            count += 1
            sum -= 1
    elif temp < 0 and sum < 0 :
        while sum <= 0 :
            count += 1
            sum += 1

if sum == 0 :
    count += 1

print(count)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

sum = a[0]
count1 = 0
count2 = 0

sum1 = 0
sum2 = 0

for i in range(n) :
    sum1 += a[i]
    sum2 += a[i]
    if i % 2 == 0 :
        if sum1 >= 0 :
            count1 += abs(sum1) + 1
            sum1 = -1
        if sum2 <= 0 :
            count2 += abs(sum2) + 1
            sum2 = 1
    elif i % 2 == 1 :
        if sum1 <= 0 :
            count1 += abs(sum1) + 1
            sum1 = 1
        if sum2 >= 0 :
            count2 += abs(sum2) + 1
            sum2 = -1

print(min(count1, count2))
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().split())
print('YES' if a - 2b + c == 0 else 'NO')


Fixed submission:
a, b, c = map(int, input().split())
print('YES' if a - 2*b + c == 0 else 'NO')
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

print(ans)

Fixed submission:
x, k, d = map(int, input().split())

def sgn(x):
    if x > 0:return 1
    if x < 0:return -1
    return 0

if x > 0:
    x_greedy = x - k * d
else:
    x_greedy = x + k * d

if sgn(x) == sgn(x_greedy):
    print(abs(x_greedy))
    exit()
x_r = x % d
x_l = x_r - d

r_parity = (abs(x - x_r) // d) % 2

if k%2 == r_parity:
    print(abs(x_r))
else:
    print(abs(x_l))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

print(ans)

Fixed submission:
n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

maximum = max(c[1:])
if maximum < 0:
    print(maximum)
    exit()

used = [False] * (n+1)

ans = 0

for i in range(1, n+1):
    if used[i]:continue
    loop = [i]
    now = i
    while p[now] != i:
        now = p[now]
        loop.append(now)

    L = len(loop)
    S = sum(c[v] for v in loop)
    for a_ind in range(L):
        a = loop[a_ind]
        used[a] = True
        dist_ab = 0
        cost_ab = -c[a]
        for b_ind in range(a_ind, a_ind+L):
            b = loop[b_ind % L]
            cost_ab += c[b]
            max_cost = cost_ab + max(0, S) * ((k - dist_ab) // L)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
given_a = list(map(int, input().split()))

money = 1000
kabu = 0

a = []

for kabuka in given_a:
    if len(a) > 0 and a[-1] == kabuka:
        continue
    else:
        a.append(kabuka)

n = len(a)
for i in range(n):
   if i == 0:
       if a[i+1] < a[i]:
           continue
       else:
           kabu += money // a[i]
           money %= a[i]
   elif i == n-1:
       money += kabu * a[i]
       kabu = 0
   else:
       if a[i-1] < a[i] and a[i] > a[i+1]:
           money += kabu * a[i]
           kabu = 0
       if a[i-1] > a[i] and a[i] < a[i+1]:
           kabu += money // a[i]
           money %= a[i]

print(money)
           
       


Fixed submission:
n = int(input())
given_a = list(map(int, input().split()))

money = 1000
kabu = 0

a = []

for kabuka in given_a:
    if len(a) > 0 and a[-1] == kabuka:
        continue
    else:
        a.append(kabuka)

n = len(a)

if n == 1:
    print(money)
    exit()
    
for i in range(n):
   if i == 0:
       if a[i+1] < a[i]:
           continue
       else:
           kabu += money // a[i]
           money %= a[i]
   elif i == n-1:
       money += kabu * a[i]
       kabu = 0
   else:
       if a[i-1] < a[i] and a[i] > a[i+1]:
           money += kabu * a[i]
           kabu = 0
       if a[i-1] > a[i] and a[i] < a[i+1]:
           kabu += money // a[i]
           money %= a[i]

print(money)
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        #todo
        nxt -= one_pow2[i]
        nxt %= one_pop_count
        print(f[nxt] + 1)
    if x[n-1-i] == '0':
        nxt = zero_mod
        #todo
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)
        

Fixed submission:
n = int(input())
x = input()

original_pop_count = x.count('1')
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_pop_count != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop_count
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count


#f の前計算

f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1

#pow2 の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        nxt %= zero_pop_count
        print(f[nxt] + 1)
Buggy python submission (verdict: Runtime Error):
MOD = 10**9 + 7

fact = [1] * 1100000
invfact = [1] * 1100000

for i in range(1, 1100000):
    fact[i] = fact[i-1] * i % MOD

invfact[1100000 - 1] = pow(fact[1100000 - 1], MOD-2, MOD)

for i in range(1100000-1, 0, -1):
    invfact[i-1] = invfact[i] * i % MOD


def nCk(n, k):
    return fact[n] * invfact[k] * invfact[n-k] % MOD


k = int(input())
n = len(input())

ans = 0

for l in range(n, n+k+1):
    ans += pow(25, l - n, MOD) * nCk(l-1, n-1) * pow(26, n+k-l, MOD) % MOD
    ans %= MOD

print(ans)

Fixed submission:
MOD = 10**9 + 7

fact = [1] * 2200000
invfact = [1] * 2200000

for i in range(1, 2200000):
    fact[i] = fact[i-1] * i % MOD

invfact[2200000 - 1] = pow(fact[2200000 - 1], MOD-2, MOD)

for i in range(2200000-1, 0, -1):
    invfact[i-1] = invfact[i] * i % MOD


def nCk(n, k):
    return fact[n] * invfact[k] * invfact[n-k] % MOD


k = int(input())
n = len(input())

ans = 0

for l in range(n, n+k+1):
    ans += pow(25, l - n, MOD) * nCk(l-1, n-1) * pow(26, n+k-l, MOD) % MOD
    ans %= MOD

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

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

dp = [0] * (s+2)

dp[0] = 1

for a in As:
    for i in range(s+1, -1, -1):
        if i - a < 0:continue
        dp[i] += dp[i-a] * (MOD+1) // 2
        dp[i] %= MOD

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

Fixed submission:
MOD = 998244353

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

dp = [0] * (s+2)

dp[0] = 1

for a in As:
    for i in range(s+1, -1, -1):
        if i - a < 0:continue
        dp[i] += dp[i-a] * (MOD+1) // 2
        dp[i] %= MOD

print(dp[s] * pow(2, n, MOD) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = map(int, input().split())

babies = [(a, i) for i, a in enumerate(a)]

babies.sort(reverse=True)

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

ans = 0

for l in range(n):
    for r in range(n):
        if l + r == n:
            ans = max(ans, dp[l][r])
            break
        activeness, ind = babies[l+r]
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)

print(ans)

Fixed submission:
n = int(input())
a = map(int, input().split())

babies = [(a, i) for i, a in enumerate(a)]

babies.sort(reverse=True)

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

ans = 0

for l in range(n):
    for r in range(n):
        if l + r == n:
            ans = max(ans, dp[l][r])
            break
        activeness, ind = babies[l+r]
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)

print(ans)