Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)


Fixed submission:
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
if cnt == 1:
    x_a = 0
else:
    x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)

Buggy python submission (verdict: Runtime Error):
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b - pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)


Fixed submission:
n = int(input())
x = input()
flg = [0] * n
for i in range(n):
    if x[i] == '1':
        flg[i] = 1
x = int(x, 2)
cnt = sum(flg)
if cnt == 1:
    x_a = 0
else:
    x_a = x % (cnt - 1)
x_b = x % (cnt + 1)


for i in range(n):
    if flg[i] == 1:
        if cnt == 1:
            print(0)
            continue
        t = (x_a - pow(2, n-i-1, cnt-1)) % (cnt - 1)
    else:
        t = (x_b + pow(2, n-i-1, cnt+1)) % (cnt + 1)

    if t == 0:
        print(1)
    else:
        tmp = 1
        while t > 0:
            pop = bin(t).count('1')
            t = t % pop
            tmp += 1

        print(tmp)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
def factorization(n):
    res = 1
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 1
            while tmp % i == 0:
                cnt += 1
                tmp //= i

            res *= cnt

        if tmp == 1:
            break
    if tmp != 1:
        res *= 2

    return res

ans = 0
for k in range(1, n+1):
    ans += k * factorization(k)

print(ans)

Fixed submission:
n = int(input())

ans = 0
for i in range(1, n+1):
    x = n // i
    ans += i * x * (x + 1) // 2

print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
mod = 10 ** 9 + 7

fac = [1 for _ in range(m+1)]
for i in range(1, m):
    fac[i+1] = fac[i] * (i+1) % mod

dp = [0 for _ in range(n+1)]
dp[1] = m - n
for i in range(2, n+1):
    dp[i] = dp[i-1] * i + fac[i-1] * (i-1)
    dp[i] %= mod


ans = dp[n]

tmp = m
for _ in range(n):
    ans *= tmp
    ans %= mod
    tmp -= 1

print(ans)1

Fixed submission:
n, m = map(int, input().split())
mod = 10 ** 9 + 7

f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, m+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

def per(n, k):
    return f[n] * f_inv[n-k] % mod

ans = 0
for i in range(0, n+1):
    res = comb(n, i) *  per(m, i) * (per(m-i, n-i) ** 2)
    if i % 2 == 1:
        res *= -1
    ans += res
    ans %= mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
mod = 10 ** 9 + 7

fac = [1 for _ in range(m+1)]
for i in range(m):
    fac[i+1] = fac[i] * (i+1) % mod
memo = [[-1 for _ in range(m+1)] for _ in range(n+1)]
for i in range(m+1):
    memo[1][i] = i-1

def g(n, m):
    if memo[n][m] != -1:
        return memo[n][m]
    
    memo[n][m] = (g(n-1, m-1) * n + fac[n-1] * (n-1)) % mod
    return memo[n][m]

ans = g(n, m)

tmp = m
for _ in range(n):
    ans *= tmp
    ans %= mod
    tmp -= 1

print(ans)

Fixed submission:
n, m = map(int, input().split())
mod = 10 ** 9 + 7

f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, m+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

def per(n, k):
    return f[n] * f_inv[n-k] % mod

ans = 0
for i in range(0, n+1):
    res = comb(n, i) *  per(m, i) * (per(m-i, n-i) ** 2)
    if i % 2 == 1:
        res *= -1
    ans += res
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k = int(input())
s = input()
n = len(s)
mod = 10 ** 9 + 7

f = [1 for _ in range(n+k+1)]
f_inv = [1 for _ in range(n+k+1)]
for i in range(n+k):
    f[i+1] = f[i] * (i+1) % mod
    f_inv[i+1] = pow(f[i+1], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

ans = 0
for i in range(k+1):
    x = pow(25, i, mod) * pow(26, k-i, mod) * comb(n-1+i, n-1)
    ans += x
    ans %= mod

print(ans)

Fixed submission:
k = int(input())
s = input()
n = len(s)
mod = 10 ** 9 + 7

f = [1, 1]
f_inv = [1, 1]
inv = [0, 1]
 
for i in range(2, n+k+1):
    f.append((f[-1] * i ) % mod)
    inv.append((-inv[mod % i] * (mod // i) ) % mod)
    f_inv.append((f_inv[-1] * inv[-1]) % mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod

ans = 0
for i in range(k+1):
    x = pow(25, i, mod) * pow(26, k-i, mod) * comb(n-1+i, n-1)
    ans += x
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])

Fixed submission:
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
flg = True
while flg and cnt < k:
    res = [0 for _ in range(n)]
    for i in range(n):
        if i - a[i] < 0:
            res[0] += 1
        else:
            res[i-a[i]] += 1

        if i + a[i] + 1 < n:
            res[i+a[i]+1] -= 1

    for i in range(n-1):
        res[i+1] += res[i] 

    if all(res[i] == n for i in range(n)):
        flg = False

    cnt += 1
    a = res.copy()

print(*a)

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

cnt = 0
flg = True
while flg and cnt < k:
    res = [0 for _ in range(n)]
    for i in range(n):
        if i - a[i] < 0:
            res[0] += 1
        else:
            res[i-a[i]] += 1

        if i + a[i] + 1 < n:
            res[i+a[i]+1] -= 1

    for i in range(n-1):
        res[i+1] += res[i] 

    if all(res[i] == n for i in range(n)):
        flg = False

    cnt += 1
    a = res.copy()

print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

pos = [pow(2, i) - a[i] for i in range(n+1)]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

for i in range(n+1):
    if pos[i] < 0:
        print(-1)
        exit()

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

pos = [0 for i in range(n+1)]
pos[0] = 1 - a[0]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

for i in range(n+1):
    if pos[i] < 0:
        print(-1)
        exit()

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

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

pos = [pow(2, i) - a[i] for i in range(n+1)]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

for i in range(n+1):
    if pos[i] < 0:
        print(-1)
        exit()

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

pos = [0 for i in range(n+1)]
pos[0] = 1 - a[0]
for i in range(n):
    pos[i+1] = pos[i] * 2 - a[i+1]

for i in range(n+1):
    if pos[i] < 0:
        print(-1)
        exit()

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, k, c = map(int, input().split())
s = input()
a = []
for i in range(n):
    if s[i] == 'o':
        a.append(i+1)

ans = []
for i in range(len(a)):
    cur = 10 ** 10
    flg = False
    for j in range(k):
        idx = bisect.bisect_left(a, cur - c) - 1
        if idx == i:
            idx -= 1
        if idx < 0:
            flg = True
            break
        cur = a[idx]


    if flg:
        ans.append(a[i])

print(*ans, sep='\n')

Fixed submission:
import bisect
n, k, c = map(int, input().split())
s = input()
a = []
for i in range(n):
    if s[i] == 'o':
        a.append(i+1)

m = len(a)
l = [0 for _ in range(m)]
r = [0 for _ in range(m)]

cur = 0
l[0] = a[0]
while True:
    to = bisect.bisect_left(a, a[cur] + c + 1)
    if to == m:
        break
    l[to] = l[cur] + 1
    cur = to

for i in range(m-1):
    if l[i] > l[i+1]:
        l[i+1] = l[i]

#print(l)

r[m-1] = 1
cur = m-1
while True:
    to = bisect.bisect_left(a, a[cur] - c) - 1
    if to == -1:
        break
    r[to] = r[cur] + 1
    cur = to

for i in range(m-1):
    x = m - 2 - i
    if r[x] < r[x+1]:
        r[x] = r[x+1]

#print(r)
l = [0] + l
r = [r[0]] + r + [0]

for i in range(1, m+1):
    if l[i-1] + r[i+1] < k:
        print(a[i-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, s = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = i + 1
mod = 998244353

ans = 0
for i in range(n):
    for j in range(s+1):
        if s > j > 0:
            dp[i+1][j] += dp[i][j]
        if j + a[i] <= s:
            dp[i+1][j+a[i]] += dp[i][j]
            dp[i+1][j+a[i]] %= mod

    ans += dp[i+1][s] * (n - i)
    ans %= mod

print(ans)

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

dp = [[0 for _ in range(s+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = i + 1
mod = 998244353

ans = 0
for i in range(n):
    for j in range(s+1):
        if s > j > 0:
            dp[i+1][j] += dp[i][j]
        if j + a[i] <= s:
            dp[i+1][j+a[i]] += dp[i][j]
            dp[i+1][j+a[i]] %= mod

    ans += dp[i+1][s] * (n - i)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        if qx == h-1 and qy == w-1:
            return d[h-1][w-1]
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w:
                d[px][py]=min(d[px][py], d[qx][qy] + (c[px][py]=='#'))
                heapq.heappush(que, (d[px][py], (px , py)))

print(bfs())

Fixed submission:
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10000000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
d = [[10000]*w for _ in range(h)]

que = []
if c[0][0] == '.':
    heappush(que, (0, 0, 0))
    d[0][0] = 0
else:
    heappush(que, (1, 0, 0))
    d[0][0] = 1

while len(que):
    dist, px, py = heappop(que)
    if d[h-1][w-1] < dist:
        break
    for dx, dy in [(0, 1), (1, 0)]:
        qx, qy = px + dx, py + dy
        if not (0 <= qx < h and 0 <= qy < w):
            continue
        if d[qx][qy] > dist:
            if c[px][py]=='.' and c[qx][qy]=='#':
                d[qx][qy] = dist + 1
                heappush(que, (d[qx][qy], qx, qy))
            else:
                d[qx][qy] = dist
                heappush(que, (d[qx][qy], qx, qy))
print(d[h-1][w-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
h, w = map(int, input().split())
c = [input() for _ in range(h)]
 
d=[[100000]*w for _ in range(h)]
 
def bfs():
    if c[0][0] == '.':
        que = [(0, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 0
    else:
        que = [(1, (0, 0))]
        heapq.heapify(que)
        d[0][0] = 1
    while len(que):
        _, (qx, qy) = heapq.heappop(que)
        if qx == h-1 and qy == w-1:
            return d[h-1][w-1]
        for dx,dy in [[1,0], [0,1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w:
                d[px][py]=min(d[px][py], d[qx][qy] + (c[px][py]=='#'))
                heapq.heappush(que, (d[px][py], (px , py)))

print(bfs())

Fixed submission:
import sys
from heapq import heappop, heappush
sys.setrecursionlimit(10000000)

h, w = map(int, input().split())
c = [input() for _ in range(h)]
d = [[10000]*w for _ in range(h)]

que = []
if c[0][0] == '.':
    heappush(que, (0, 0, 0))
    d[0][0] = 0
else:
    heappush(que, (1, 0, 0))
    d[0][0] = 1

while len(que):
    dist, px, py = heappop(que)
    if d[h-1][w-1] < dist:
        break
    for dx, dy in [(0, 1), (1, 0)]:
        qx, qy = px + dx, py + dy
        if not (0 <= qx < h and 0 <= qy < w):
            continue
        if d[qx][qy] > dist:
            if c[px][py]=='.' and c[qx][qy]=='#':
                d[qx][qy] = dist + 1
                heappush(que, (d[qx][qy], qx, qy))
            else:
                d[qx][qy] = dist
                heappush(que, (d[qx][qy], qx, qy))
print(d[h-1][w-1])
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
q=int(input())

for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        s=s[::-1]
    else:
        if query[1]=='1':
            s=[query[2]]+s
        else:
            s+=[query[2]]
print(*s,sep='')

Fixed submission:
from collections import deque

s=input()
q=int(input())
d=deque(s)

cnt=0
for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        cnt=(cnt+1)%2
    else:
        if query[1]=='1':
            if cnt==1:
                d.append(query[2])
            else:
                d.appendleft(query[2])
        else:
            if cnt==1:
                d.appendleft(query[2])
            else:
                d.append(query[2])
                
ans=list(d)
                
if cnt==1:
    print(*ans[::-1],sep='')
else:
    print(*ans,sep='')

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())

for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        s=s[::-1]
    else:
        if query[1]=='1':
            s=query[2]+s
        else:
            s+=query[2]
print(s)

Fixed submission:
from collections import deque

s=input()
q=int(input())
d=deque(s)

cnt=0
for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        cnt=(cnt+1)%2
    else:
        if query[1]=='1':
            if cnt==1:
                d.append(query[2])
            else:
                d.appendleft(query[2])
        else:
            if cnt==1:
                d.appendleft(query[2])
            else:
                d.append(query[2])
                
ans=list(d)
                
if cnt==1:
    print(*ans[::-1],sep='')
else:
    print(*ans,sep='')
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
memo = {}
def search(x):
    if x in memo:
        return memo[x]

    sx = str(x)
    sn = len(sx)

    if sn == 1:
        if x <= 5:
            return x
        else:
            return 11 - x

    if int(sx[0]) < 9:
        p = int(sx[0]) + 1
    else:
        p = 1
    res1 = search(int(sx[1:])) + int(sx[0])
    res2 = search((int(sx[0]) + 1) * (10 ** (sn - 1)) - x) + p

    memo[x] =  min(res1, res2)
    return memo[x]

print(search(n))

Fixed submission:
n = input()
x = len(n)
inf = 10 ** 9
#dp[i][flg]...i桁目まで、未満フラグ=1
dp = [[inf] * 2 for _ in range(x+1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(x):
    s = int(n[i])
    dp[i+1][0] = min(dp[i][0] + s, dp[i][1] + 10 - s)
    dp[i+1][1] = min(dp[i][0] + s + 1, dp[i][1] + 9 - s)

print(dp[x][0])
Buggy python submission (verdict: Time Limit Exceeded):
#154_D
n, k = map(int, input().split())
p = [(int(x)+1) / 2 for x in input().split()]

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(p[i:i+k]))
print(ans)

Fixed submission:
#154_D
n, k = map(int, input().split())
p = list(map(int, input().split()))

tmp = sum(p[0:k])
ans = tmp
for i in range(1,n-k+1):
    tmp += p[i+k-1] - p[i-1]
    ans = max(ans, tmp)

print((ans + k) / 2)

Buggy python submission (verdict: Time Limit Exceeded):
#154_D
n, k = map(int, input().split())
p = [(int(x)+1) / 2 for x in input().split()]

ans = 0
for i in range(n-k+1):
    ans = max(ans, sum(p[i:i+k]))
print(ans)

Fixed submission:
#154_D
n, k = map(int, input().split())
p = list(map(int, input().split()))

tmp = sum(p[0:k])
ans = tmp
for i in range(1,n-k+1):
    tmp += p[i+k-1] - p[i-1]
    ans = max(ans, tmp)

print((ans + k) / 2)
Buggy python submission (verdict: Time Limit Exceeded):
r1, c1, r2, c2 = map(int, input().split())

n = r2 + c2 + 3
mod = 10 ** 9 + 7
f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod
def g(r, c):
    return comb(r+c+2, c+1) - 1

ans = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ans %= mod

print(ans)

Fixed submission:
r1, c1, r2, c2 = map(int, input().split())

n = r2 + c2 + 3
mod = 10 ** 9 + 7
f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod
def g(r, c):
    return comb(r+c+2, c+1) - 1

ans = g(r2, c2) - g(r2, c1-1) - g(r1-1, c2) + g(r1-1, c1-1)
ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#153_E
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
print(dp[h])

Fixed submission:
#153_E
h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
dp = [10 ** 10 for _ in range(h+1)]
dp[0] = 0
for i in range(1, h+1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i-a, 0)] + b)
print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
cnt = 0
for i in range(n):
    if h[i] <= 0:
        continue
        
    idx = bisect_right(x, x[i] + 2 * d)
    cur_cnt = -(-h[i] // a)
    for j in range(i, idx):
        h[j] -= cur_cnt * a
    
    cnt += cur_cnt
    
print(cnt)

Fixed submission:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
cnt = 0
for i in range(n):
    if h[i] <= 0:
        continue
        
    idx = bisect_right(x, x[i] + 2 * d)
    cur_cnt = -(-h[i] // a)
    for j in range(i, idx):
        h[j] -= cur_cnt * a
    
    cnt += cur_cnt
    
print(cnt)

Fixed submission:
#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
#147_D
n = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7

for i in range(60):
    s = sum([(a >> i) & 1 for a in A])
    ans = (ans + s * (n-s) * pow(2,i,mod)) % mod
print(ans)

Fixed submission:
#147_D
n = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10 ** 9 + 7

for i in range(60):
    s = sum([(a >> i) & 1 for a in A])
    ans = (ans + s * (n-s) * pow(2,i,mod)) % mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#三井住友2019_D
n=int(input())
s=input()

cnt=0
for i in range(0,1000):
    t='0'*(3-len(str(i)))+str(i)
    flg1,flg2,flg3=[False]*3
    for j in range(n):
        if flg1:
            if flg2:
                if s[j]==t[2]:
                    flg3=True
                    break
            else:
                if s[j]==t[1]:
                    flg2=True
        else:
            if s[j]==t[0]:
                flg1=True
    cnt+=1 if flg3 else 0
    
print(cnt)



Fixed submission:
#三井住友2019_D
n=int(input())
s=input()

cnt=0
for i in range(0,1000):
    t='0'*(3-len(str(i)))+str(i)
    flg1,flg2,flg3=[False]*3
    for j in range(n):
        if flg1:
            if flg2:
                if s[j]==t[2]:
                    flg3=True
                    break
            else:
                if s[j]==t[1]:
                    flg2=True
        else:
            if s[j]==t[0]:
                flg1=True
    cnt+=1 if flg3 else 0
    
print(cnt)