Problem: Silver Fox is fighting with N monsters.  The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate X_i, has the _health_ of H_i.  Silver Fox can use bombs to attack the monsters. Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A. There is no way other than bombs to decrease the monster's health.  Silver Fox wins when all the monsters' healths become 0 or below.  Find the minimum number of bombs needed to win.

Submission attempts (in order):
import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [0 for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]
    rang[i] = x

num = 0
xh.sort(key=lambda xh:xh[0])]

dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        for j in range(i+1,n):
            if rang[j] <= pos + 2d:
                dam[j] += a*nat
            else:
                break
print(num)


import numpy as np

n, d, a = map(int,input().split())
xh = np.zeros((n,2), dtype = int)
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh = xh[np.argsort(xh[:, 0])]

while xh.size > 0.5:
    if xh[0,1]%a == 0:
        nat = int((xh[0,1])/a)
    else:
        nat = int((xh[0,1])/a+1)
    num += nat
    dam = nat*a
    for i in range(xh.shape[0]):
        if xh[i,0] <= xh[0,0]+2*d:
            xh[i,1] -= dam
        else:
            break
    xh = xh[np.all(xh<0.5,axis=1)]

print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(n):
            if math.fabs(xh[j][0]-pos) <= d:
                ###dam[j] += a*nat

print(num)


import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [0 for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]
    rang[i] = x
print(xh,rang)

num = 0
xh.sort(key=lambda xh:xh[0])

dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        for j in range(i+1,n):
            if rang[j]-d <= pos + d:
                dam[j] += a*nat
            else:
                break
print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n
rang = [0]*n
for i in range(n):
    rang[i] = xh[i][0]-d
'''
for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(n):
            if rang[j] <= pos:
                dam[j] += a*nat
            else:
                break
'''
print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
x = []
h = []

'''
while len(h) > 0.5:
    nat = math.ceil((h[0])/a)
    num += nat
    dam = nat*a
    for i in range(len(x)):
        if x[i] <= x[0]+2*d:
            h[i] -= dam
        else:
            break
    while len(h) > 0 and h[0] < 0.5:
        h.pop(0)
        x.pop(0)
'''

print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n
rang = [0]*n
for i in range(n):
    rang[i] = xh[i][0]

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(n):
            if rang[j] <= pos:
                dam[j] += a*nat

print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
print(xh)

while len(xh) > 0.5:
    nat = math.ceil((xh[0][1])/a)
    num += nat
    dam = nat*a
    for i in range(len(xh)):
        if xh[i][0] <= xh[0][0]+2*d:
            xh[i][1] -= dam
        else:
            break
    xh = [i for i in xh if i[1] > 0]

print(num)


import numpy as np
import math

n, d, a = map(int,input().split())
xh = np.zeros((n,2), dtype = int)
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh = xh[np.argsort(xh[:, 0])]


print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n
rang = [0]*n
for i in range(n):
    rang[i] = xh[i][0]-d

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
        for j in range(i+1,n):
            if rang[j] <= pos:
                dam[j] += a*nat
                print(j,dam[j])
            else:
                break
print(num)


import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [n]*(n-1)+[0]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(rang[i-1],n):
        if xh[i][0]+d < xh[j][0]-d:
            rang[i] = j
            break

dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        '''
        for j in range(i+1,rang[i]):
            dam[j] += a*nat
            '''
print(num)


import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [n]*(n-1)+[0]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(rang[i-1],n):
        if xh[i][0]+d < xh[j][0]-d:
            rang[i] = j
            break

'''
dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        for j in range(i+1,rang[i]):
            dam[j] += a*nat
'''
print(num)


import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
rang = [n]*n
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(rang[i-1],n):
        if xh[i][0]+d < xh[j][0]-d:
            rang[i] = j
            break
print(rang)

dam = [0]*n
for i in range(n):
    res = xh[i][1]-dam[i]
    pos = xh[i][0]
    if res > 0:
        nat = math.ceil(res/a)
        num += nat
        for j in range(i+1,rang[i]):
            dam[j] += a*nat

print(num)


import math

n, d, a = map(int,input().split())
xh = []
for i in range(n):
    x,h = map(int,input().split())
    xh.append([x,h])

num = 0
xh.sort(key=lambda xh:xh[0])
l = len(xh)
dam = [0]*n

for i in range(n):
    res = xh[i][1]-dam[i]
    if res > 0:
        nat = math.ceil(res/a)
        pos = xh[i][0]+d
        num += nat
'''
        for j in range(n):
            if math.fabs(xh[j][0]-pos) <= d:
                dam[j] += a*nat
'''

print(num)


import math

n, d, a = map(int,input().split())
xh = [[0 for i in range(2)] for j in range(n)]
left = [i for i in range(n)]
for i in range(n):
    x,h = map(int,input().split())
    xh[i] = [x,h]

num = 0
xh.sort(key=lambda xh:xh[0])

for i in range(n):
    for j in range(left[i-1],i):
        if xh[j][0]+d >= xh[i][0]-d:
            left[i] = j
            break

dam = [0]*n

def dsum(k):
    if k == 0:
        return 0
    elif left[k] == 0:
        return dam[k-1]
    else:
        return dam[k-1]-dam[left[k]-1]

for i in range(n):
    res = xh[i][1]-dsum(i)
    nat = max([math.ceil(res/a),0])
    dam[i] = dam[i-1]+a*nat
    if res > 0:
        num += nat

print(num)


Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted