Problem:


Score : 600 points

Problem Statement

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.

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq D \leq 10^9

1 \leq A \leq 10^9

0 \leq X_i \leq 10^9

1 \leq H_i \leq 10^9

X_i are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N D A
X_1 H_1
:
X_N H_N

Output

Print the minimum number of bombs needed to win.

Sample Input 1

3 3 2
1 2
5 4
9 2

Sample Output 1

2

First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2.

Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2.

Now, all the monsters' healths are 0.
We cannot make all the monsters' health drop to 0 or below with just one bomb.

Sample Input 2

9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5

Sample Output 2

5

We should use five bombs at the coordinate 5.

Sample Input 3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

Sample Output 3

3000000000

Watch out for overflow.



Sample input:
3 3 2
1 2
5 4
9 2


Sample output:
2

Submission status: Runtime Error

Solution code:
import math
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法2 - imos法
"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""

#process1
index = 0
reach = []
for i in range(n):
    for j in range(i+1,n):
        if lst1[j][0] <= lst1[i][0] + 2*d: #届くなら
            index += 1
        else:
            break
    reach.append(index)

#process2
ans = 0
imos = [0]*(n+1) #その座標に効いている魔法の回数(ダメージ量ではない)

for i in range(n):
    if imos[i]*a < lst1[i][1]: #ダメージが足りないなら
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]+1] -= need #届かなくなったとこでマイナス
        ans += need
    imos[i+1] += imos[i] #累積和を逐一とる

print(ans)

Submission status: Runtime Error

Solution code:
N,D,A=map(int,input().split())
P=sorted([list(map(int,input().split())) for i in range(N)])
l=r=a=d=0
m=[0]*(N+1)
while l<N:
    while r<N and P[r][0]<=P[l][0]+2*D:
        r+=1
    d+=m[l]
    x=-(-max(0,P[l][1]-d)//A)
    a+=x
    d+=x*A
    dm[r]-=x*A
    l+=1
print(a)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
def getVal(i):  # get value of node (i,i)
    v = T[(i,i)][0]
    cur = (i,i)
    cur = T[cur][1]
    while cur[0]>=0:
        v += T[cur][0]
        cur = T[cur][1]
    return v
def udT(i,j,x,node):  # add x between [i,j] where current node is given
    l,r = node[0],node[1]
    if i<=l and r<=j:
        T[node][0] += x
    elif i>r or j<l:
        return
    else:
        udT(i,j,x,T[node][2])
        udT(i,j,x,T[node][3])
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
n = 0
m = N
while m>0:
    m = m//2
    n += 1
if N==2**(n-1):
    n -= 1
for i in range(N,2**n):  # fill in the remainder of N
    X.append([X[-1][0]+1,0])
# Construction of Tree
Y = [X[i][0] for i in range(N)]  # Tree structure
T = {(i,i):[X[i][1],(i,i+1) if i%2==0 else (i-1,i),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
for h in range(n):
    for i in range(2**h):
        d = 2**(n-h)  # interval length of each node
        if h==0:
            T[(i*d,(i+1)*d-1)] = [0,(-1,-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
        else:
            T[(i*d,(i+1)*d-1)] = [0,(i*d,i*d+2*d-1) if (i*d)%2**(n-h+1)==0 else ((i+1)*d-2*d,(i+1)*d-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
cnt = 0
cur = 0
while cur<N:
    x = Y[cur]
    v = getVal(cur)
    if v%A==0:
        k = v//A
    else:
        k = v//A+1
    ind = bisect_right(Y,x+2*D)
    udT(cur,ind-1,-k*A,(0,2**n-1))
    cnt += k
    flag = 0
    for i in range(cur+1,N):
        if getVal(i)>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Submission status: Runtime Error

Solution code:
import math
from bisect import bisect_right
def getVal(i):  # get value of node (i,i)
    v = T[(i,i)][0]
    cur = (i,i)
    cur = T[cur][1]
    while cur[0]>=0:
        v += T[cur][0]
        cur = T[cur][1]
    return v
def udT(i,j,x,node):  # add x between [i,j] where current node is given
    l,r = node[0],node[1]
    if i<=l and r<=j:
        T[node][0] += x
    elif i>r or j<l:
        return
    else:
        udT(i,j,x,T[node][2])
        udT(i,j,x,T[node][3])
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
n = math.ceil(math.log2(N))
for i in range(N,2**n):  # fill in the remainder of N
    X.append([X[-1][0]+1,0])
# Construction of Tree
Y = [X[i][0] for i in range(N)]  # Tree structure
T = {(i,i):[X[i][1],(i,i+1) if i%2==0 else (i-1,i),(-1,-1),(-1,-1)] for i in range(2**n)}  # T[node] = [value,parent,left_child,right_child]
for h in range(n):
    for i in range(2**h):
        d = 2**(n-h)  # interval length of each node
        if h==0:
            T[(i*d,(i+1)*d-1)] = [0,(-1,-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
        else:
            T[(i*d,(i+1)*d-1)] = [0,(i*d,i*d+2*d-1) if (i*d)%2**(n-h+1)==0 else ((i+1)*d-2*d,(i+1)*d-1),(i*d,i*d+d//2-1),((i+1)*d-d//2,(i+1)*d-1)]
cnt = 0
cur = 0
while cur<N:
    x = Y[cur]
    v = getVal(cur)
    if v%A==0:
        k = v//A
    else:
        k = v//A+1
    ind = bisect_right(Y,x+2*D)
    udT(cur,ind-1,-k*A,(0,2**n-1))
    cnt += k
    flag = 0
    for i in range(cur+1,N):
        if getVal(i)>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)

Submission status: Runtime Error

Solution code:
import bisect

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]


class BIT:
    def __init__(self, n=None):
        # 1-index
        if n is None:
            n = (1 << 20) - 1
        self.n = n
        self.dat_a = [0] * (2 * self.n - 1)
        self.dat_b = [0] * (2 * self.n - 1)

    def add(self, a, b, x, k=0, l=0, r=None):
        # Add x to [a, b)
        if r is None:
            r = self.n

        if a <= l and r <= b:
            self.dat_a[k] += x
        elif l < b and a < r:
            self.dat_b[k] += (min(b, r) - max(a, l)) * x
            self.add(a, b, x, k * 2 + 1, l, (l + r) // 2)
            self.add(a, b, x, k * 2 + 2, (l + r) // 2, r)
            
    def query(self, a, b, k=0, l=0, r=None):
        # Retrun sum of [a, b)
        if r is None:
            r = self.n
        
        if b <= l or r <= a:
            return 0
        
        if a <= l and r <= b:
            return self.dat_a[k] * (r - l) + self.dat_b[k]
        
        res = (min(b, r) - max(a, l)) * self.dat_a[k]
        res += self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        res += self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        
        return res

X, H = zip(*sorted(XH))
bit = BIT(N + 10)

# 初期化
for i, h in enumerate(H):
    bit.add(i + 1, i + 2, h)
    
# 処理
res = 0
for i in range(N):
    cur = bit.query(i + 1, i + 2)
    if cur <= 0:
        continue

    need = -(-cur // A)
    idx = bisect.bisect_right(X, X[i] + 2 * D)
    bit.add(i + 1, idx + 1, -need * A)
    res += need
    
print(res)

Submission status: Runtime Error

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l.sort()
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  s=set()
  for j in range(i,n):
    if abs(d-l[j][0])<=D:
      s.add(j)
    else:break
  for k in s:
    l[k][1]-=time*A
  ans+=time
print(ans)

Submission status: Runtime Error

Solution code:
import math
N,D,A=map(int,input().split())
l=[]
for i in range(N):
  k=list(map(int,input().split()))
  l.append(k)
l=l.sort()
ans=0
for i in range(N):
  h=l[i][1]
  if h<=0:continue
  d=l[i][0]+D
  time=math.ceil(h/A)
  s=set()
  for j in range(i,n):
    if abs(d-l[j][0])<=D:
      s.add(j)
    else:break
  for k in s:
    l[k][1]-=time*A
  ans+=time
print(ans)

Submission status: Runtime Error

Solution code:
N,D,A = map(int,input().split())
d = {}
E = []
for i in range(N):
    x,h = map(int,input().split())
    d[x] = h
    E.append(x)
E.sort()
ans = 0
import bisect
for i in range(N):
    x = E[i]
    if d[x] <= 0:
        continue
    y = bisect.bisect_right(E,x+2*D)
    ans += d[x]
    for j in range(i,y):
        d[j] -= d[x]
print(ans)

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
monster = []
for _ in range(n):
  x, h = map(int, input().split())
  monster.append((x, h))
monster.sort()
bomb = 0
j = 0
for i in range(n):
  while monster[j][0] - monster[i][0] <= 2 * d and j < n:
    j += 1
  if monster[i][1] <= 0:
    continue
  b = (monster[i][1] - 1) // a + 1
  atk = a * b
  bomb += b
  for k in range(i+1, j):
    monster[k][1] -= atk
print(bomb)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
n,d,a=map(int,input().split())
xh=[list(map(int,input().split()))for _ in range(n)]
xh.sort()
x=[]
h=[]
for xx,hh in xh:
  x.append(xx)
  h.append(hh)

not_imos=[0]*(n+1)
atk_n=0
ans=0
for i in range(n):
  atk_n-=imos[i]
  h[i]-=atk_n*a
  if h[i]<0:h[i]=0
  atk_i=0--h[i]//a
  ans+=atk_i
  atk_n+=atk_i
  imos[bisect_right(x,x[i]+d*2)]+=atk_i
print(ans)

Submission status: Runtime Error

Solution code:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:　
        ##ms[i][1]-=tmp　二回引いてるわ
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
N, D, A = map(int, input().split())

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,i))
    hs.append(-(-H//A))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = 0
dmg = 0
r = 0
for y, i in ys:
    while l <= y:
        li += 1
        l = ys[li][0] + 2*D
        dmg -= hs[ys[li][1]]
    tr = max(0, hs[i]-dmg)
    hs[i] = tr
    dmg += tr
    r += tr
print(r)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(10 ** 7)

N, D, A = map(int, input().split())

E = []
for _ in range(N):
    x, h = map(int, input().split())
    E.append((x, h))


E = sorted(E, key=lambda x: x[0])

damage = 0
BOMB = defaultdict(int)
x = 0
ans = 0
for i in range(N):
    x, h = E[i]

    dlt = []
    for xd, d in BOMB.items():
        if x > xd:
            damage -= d
            dlt.append(xd)
    for dl in dlt:
        BOMB.pop(dl)

    h -= damage

    if h <= 0:
        continue
    xm = x + 2 * D
    cnt = -1 * (-h // A)
    damage += cnt * A
    BOMB[xm] = cnt * A
    ans += cnt

print(ans)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
AB = []
 
for i in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
    
INF = 10**15
M = 2*10**4

dp = [[INF]*(M+1) for i in range(N+1)]

for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    A,B = AB[i]
    for j in range(A):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    for j in range(H)
        dp[i+1][j+A] = min(dp[i][j+A], dp[i+1][j]+B, dp[i+1][j+A])
        
ans = INF
for i in range(H,M):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Runtime Error

Solution code:
import math

N,d,a = map(int, input().split())
xh = sorted([list(map(int, input().split())) for i in range(N)], key=itemgetter(0))
x = []
for X,h in xh:
  x.append(X)
data0 = [0]*(N+1)
data1 = [0]*(N+1)

def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

ans = 0

for L,(X,H) in enumerate(xh):
  L += 1
  R = bisect.bisect_right(x,X+2*d)
  res = math.ceil((H - query(L,L+1) * a) / a) #ansを変える
  ans += res
  add(L,R+1,res)
print(ans)

Submission status: Runtime Error

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=itemgetter(0))

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    if len(pq) and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

print(ans)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
AB = []
 
for i in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
INF = 10**15
dp = [[INF]*(2*10**4+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
 
for i in range(N):
    for j in range(1,2*10**4+1):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-AB[i][0]]+AB[i][1])
        
ans = float('inf')
for i in range(H,2*10**4+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Runtime Error

Solution code:
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort(key=itemgetter(0))

import collections
q=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    if len(q) and q[0][0] < x:
        totalDamage -= q[0][1]
        q.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    q.append((x+2*d,dam))

print(ans)

Submission status: Runtime Error

Solution code:
N,D,A=[int(i) for i in input().split()]
tempX,tempH=[],[]
for _ in range(N):
    x,h=[int(i) for i in input().split()]
    tempX.append(x)
    tempH.append(h)
x_max=max(tempX)

H=[0]*(x_max+1)
i=0
for x in tempX:
    H[x]=tempH[i]
    i+=1

# def center(H):
#     m=0
#     for i in range(x_max):
#         r=max(0,i-D)
#         l=min(x_max,i+D)
#         if len(H[r:l+1])>m:
#             m=len(H[r:l+1])
#             c=i
#             res_r=r
#             res_l=l
#     return (c,res_r,res_l)

ans=0
#
# r,l=0,4
# print(H)
# H[r:l+1]=list(map(lambda x:x-A,H[r:l+1]))
# print(H)

while max(H)>0:
    m=0
    for i in range(x_max):
        temp_r=max(0,i-D)
        temp_l=min(x_max,i+D)
        I=[i for i in H[temp_r:temp_l+1] if i>0]
        if len(I)>m:
            m=len(I)
            r=temp_r
            l=temp_l
    H[r:l+1]=list(map(lambda x:x-A,H[r:l+1]))
    ans+=1

print(ans)

Submission status: Runtime Error

Solution code:
# TLE
import math
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_list = [0]*N
hp_dict = dict()
for j in range(N):
    monster_place, monster_hp = map(int, input().split())
    place_list[j] = monster_place
    hp_dict[monster_place] = monster_hp
ans = 0
place_list = sorted(place_list)
new_place_dict = dict()
for s in range(N):
    new_place_dict[s] = place_list[s]

# print(place_list)
for i in range(N):
    place = place_list[i]
    if hp_dict[place] <= 0:
        continue
    else:
        bomb = math.ceil(hp_dict[place] / A)
        # print(bomb)
        ans += bomb
        index = i
        while(place_list[index] <= place+2*D and index < N):
            if hp_dict[new_place_dict[index]] <= 0:
                index += 1
                continue
            else:
                hp_dict[new_place_dict[index]] -= bomb * A
                index += 1

print(ans)
# print(hp_dict)

Submission status: Runtime Error

Solution code:
# TLE
import math
N, D, A = map(int, input().split())
monsterlist = [0] * N
place_list = [0]*N
hp_dict = dict()
for j in range(N):
    monster_place, monster_hp = map(int, input().split())
    place_list[j] = monster_place
    hp_dict[monster_place] = monster_hp
ans = 0
place_list = sorted(place_list)
new_place_dict = dict()
for s in range(N):
    new_place_dict[s] = place_list[s]

# print(place_list)
for i in range(N):
    place = place_list[i]
    if hp_dict[place] <= 0:
        continue
    else:
        bomb = math.ceil(hp_dict[place] / A)
        # print(bomb)
        ans += bomb
        index = i
        while(place_list[index] <= place+2*D):
            if hp_dict[new_place_dict[index]] <= 0:
                index += 1
                continue
            else:
                hp_dict[new_place_dict[index]] -= bomb * A
                index += 1

print(ans)
# print(hp_dict)

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = np.array([-(-i//a) for i in H])
ans = 0
for now in range(n):
  l = K[now]
  if l > 0:
    ans += l
      K[now:bisect.bisect_right(X, X[now]+2*d)] -= l
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys

input = sys.stdin.readline
N, D, A = map(int, input().split())
XH = []
for i in range(N):
    XH.append([(map(int, input().split()))])
XH.sort()
ans = 0
for i, name in enumerate(XH):
    if name[1] > 0:
        p = name[0]
        t = A * math.ceil(name[1] / A)
        ans += math.ceil(name[1] / A)
        for l in XH[i::]:
            if l[0] <= p + 2 * D:
                l[1] -= t
            else:
                break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

tg = sorted(tg, key=lambda x:x[0])
bit = BIT(n+2)
result = 0
ind = 0
for i in range(n):
    c = tg[i][1] - bit.sum(i+1)
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    if ind < c:
        ind = c
    for j in range(ind, n):
        if tg[j][0] <= wd:
            ind = j
        else:
            break
    bit.add(i+1, c)
    bit.add(ind+2, -c)
    for j in range(n+1):
print(result)

Submission status: Runtime Error

Solution code:
import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t 
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

H,N = I()
for i in range(N):
    A,B = I()
    L1.append([A,B,A/B])
L2 = sorted(L1,reverse=True,key=lambda x: x[2])
ans = 0
for i in range(10):
    for e in L2:
        if H >= e[0]:
            ans += H//e[0] * e[1]
            H = H%e[0]
            print(ans,H)
            break
print(ans,H)
L3 = sorted(L1,key=lambda x: x[1])
P2(L3)
if H > 0:
    for e in L3:
        if H <= e[0]:
            ans += e[1]
            break
print(ans,H)

Submission status: Runtime Error

Solution code:
H,N = map(int,input().split())
AB = []
 
for i in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])

dp = [[float('inf')]*(H+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    for j in range(H):
        dp[i+1][min(j+AB[i][0],H)] = min(dp[i][min(j+AB[i][0],H)],dp[i+1][j]+AB[i][1],dp[i+1][min(j+AB[i][0],H)])
        
print(dp[N][H])

Submission status: Runtime Error

Solution code:
N, D, A=(int(i) for i in input().split())
P=[[int(i) for i in input().split()] for  _ in range(N)]
P=sorted(P, key=lambda x:x[0])

ans=0

for i in range(N):
    if P[i][1]>0:
        if P[i][1]%A==0:
            bomb=P[i][1]//A
        else:
            bomb=P[i][1]//A+1
        ans+=bomb
        for j in range(i,N):
            if P[j][0]<=P[i][0]+2*D:
                P[j][1]-=A*bomb
                if P[j][1]<=0:
                    del P[j]
            else:
                break
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

n, d, a = map(int, input().split())
xh = []
x_list = []
for i in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
    x_list.append(x)
xh.sort()
x.sort()
count = 0
min_x = 0
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    flag = True
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    for i in range(min_x, bisect.bisect(x_list, place + d)):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            if flag == True:
                min_x += 1
        else:
            flag = False
        xh[i][1] = new_h
print(count)

Submission status: Runtime Error

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*(10**4+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4+1):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4+1):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Runtime Error

Solution code:
import numpy as np
n,d,a=map(int,input().split())
flag=np.zeros(10**9+1)
XH=[list(map(int,input().split())) for _ in range(n)]
XH.sort(key=lambda A:A[0])
cnt=0
for i in range(n):
    kaisu=0
    x,h=XH[i]
    if flag[x]==0:
        kaisu=(h+a-1)//a
        flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
        cnt+=kaisu
    else:
        if flag[x]<h:
            h-=flag[x]
            kaisu=(h+a-1)//a
            flag[x:min((x+2*d+1),10**9+1)]+=kaisu*a
            cnt+=kaisu
print(int(cnt))

Submission status: Runtime Error

Solution code:
import math
N, D, A = map(int, input().split())
L=[]
maximum=0
for i in range(N):
    X=list(map(int, input().split()))
    maximum=max(maximum,X[0])
    L.append(X)
L.sort()
num=[0]*(maximum+1)
k=0
for j in range(maximum+1):
    if j<L[k][0]:
        num[j]=k-1
    else:
        num[j]=k
        k=min(N-1,k+1)
count=0
for i in range(N):
    if L[i][1]>0:
        distance=num[min(L[i][0]+2*D,maximum)]
        for j in range(i,distance+1):
            L[j][1]=L[i][1]-A*math.ceil(L[i][1]/A)
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
N, D, A = map(int, input().split())
XH = [[0,0] for i in range(N)]
for i in range(N):
    XH[i][0], XH[i][1] = map(int, input().split())
XH.sort()
now = XH[0][0]
i = 0
tmp = 10**9
cnt = 0
while XH[-1][1] > 0:
    tmp = 10**9
    while XH[i][0] <= now + 2 * D:
        if XH[i][1] > 0:
            XH[i][1] -= now
            cnt += 1
        if XH[i][1] > 0:
            tmp = min(tmp, i)
        i += 1
    
    now = XH[min(tmp, i+1)][1]
    i = tmp
print(cnt)

Submission status: Runtime Error

Solution code:
N, D, A = map(int, input().split())
XH = [[0,0] for i in range(N)]
for i in range(N):
    XH[i][0], XH[i][1] = map(int, input().split())
XH.sort()
now = XH[0][0]
i = 0
tmp = 10**9
cnt = 0
while XH[-1][1] > 0:
    tmp = 10**9
    while XH[i][0] <= now + 2 * D:
        if XH[i][1] > 0:
            XH[i][1] -= now
            cnt += 1
        if XH[i][1] > 0:
            tmp = min(tmp, i)
        i += 1
    
    now = XH[min(tmp, i+1][1]
    i = tmp
print(cnt)

Submission status: Runtime Error

Solution code:
N, D, A=(int(i) for i in input().split())
P=[[int(i) for i in input().split()] for  _ in range(N)]
P=sorted(P, key=lambda x:x[0])


ans=0
bomb_x=[]
for i in range(N):
    atack=0
    for j in range(len(bomb_x)):
        if (bomb_x[j]+D>P[i][0]) and (bomb_x[j]-D<P[i][0]):
            atack+=1
    if P[i][0]-atack*A>0:
        if P[i][1]%A==0:
            bomb=(P[i][0]-atack*A)//A
        else:
            bomb=(P[i][0]-atack*A)//A+1
        ans+=bomb
        bomb_x.extend([P[i][0]+D]*bomb)
print(ans)

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
lst = []
for i in range(n):
    xi, hi = map(int, input().split())
    if hi % a == 0:
        hi = hi // a
    else:
        hi = hi // a + 1
    lst.append([xi, hi])
lst.sort(key=lambda x: x[0])
x, h = [], []
for i in range(n):
    x.append(lst[i][0])
    h.append(lst[i][1])

x.append(10**11)
h.append(0)

kougeki_start = 0
kougeki_end = 0
cnt = 0
i = 0
while i <= n:
    if h[i] > 0:
        left = i # 可能
        right = n # 不可能
        while left+1 < right:
            mid = (left + right) // 2
            if x[mid] - x[i] <= 2*d:
                left = mid
            else:
                right = mid
        cnt += h[i]
        hiku = h[i]
        bit = 0
        for j in range(i, left+1):
            h[j] -= hiku
            if bit == 0 and h[j] > 0:
                next_i = j
                bit = 1
        i = next_i

print(cnt)

Submission status: Runtime Error

Solution code:
import math
from collections import deque

N, D, A = map(int, input().split())
# XHs = [tuple(map(int, input().split())) for _ in range(N)]
Q = deque([0] * D)

HPs = [0] * 10 ** 9
for _ in range(N):
    X, H = map(int, input().split())
    HPs[X] = H

ans = 0
for i in range(D, 10 ** 1 + D + 1):
    num = max(math.ceil((HPs[i - D] - sum(Q)) // A), 0)
    atk = num * A
    Q.popleft()
    Q.append(atk)
    ans += num
print(ans)

Submission status: Runtime Error

Solution code:
s = input().split()
n = int(s[0])
d = int(s[1])
a = int(s[2])
l = []
for i in range(n):
    l.append([int(k) for k in input().split()])
l = sorted(l, key = lambda x:(x[0]))
x = l[0][0] + d
answer = 0
now = 0
while(l[n-1][1]>0):
    while(l[now][1]>0):
        answer = answer + 1
        for p in range(len(l)):
            if((x-d)<= l[p][0] && l[p][0]<=(x+d)):
                l[p][1] = l[p][1] - a
    while(l[now][1]<=0):
        if(now==len(l)-1):
            break
        now = now +1
        x = l[now][0] + d
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
n,d,a = map(int,input().split())
mons=[]
for i in range(n):
    x,h=map(int,input().split())
    mons.append([x,h])
mons.sort()
damages = np.zeros(n)
right_idx=0

cnt = 0
for i in range(n):
    x,h = mons[i]
    h -= damages[i]
    if h<0:
        continue
    left_x = x
    left_idx = i
    right_x = x + 2*d
    tmp=0
    while(1):
        if right_idx+tmp == n or mons[right_idx+tmp][0]>right_x:
            right_idx += tmp
            break
        tmp+=1
    c = int(h//a + int(bool(h%a)))
    damage = a*c
    cnt += c
    d_list = [damage*(i>=left_idx)*(i<=right_idx) for i in range(n)]
    damages = list(map(lambda x,y:x+y,damages,d_list))
print(cnt)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n, di, a = LI()
    xs = []
    d = {}
    q = []
    for i in range(n):
        x, h = LI()
        xs.append(x)
        if h % a == 0:
            d[x] = h // a
        else:
            d[x] = h // a + 1
    sorted_xs = sorted(xs)
    ans = 0
    for i in range(n):
        
        if d[sorted_xs[i]] < 1:
            continue
        else:
            ans += d[sorted_xs[i]]
            for j in range(1, n):
                if sorted_xs[i + j] <= sorted_xs[i] + 2 * di:
                    d[sorted_xs[i + j]] -= d[sorted_xs[i]]
                else:
                    break
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
H, D, A = map(int, input().split())
L=[]
maximum=0
for i in range(N):
    X=list(map(int, input().split()))
    maximum=max(maximum,X[0])
    L.append(X)
L.sort()
num=[0]*(maximum+1)
k=0
for j in range(maximum+1):
    if j<L[k][0]:
        num[j]=k-1
    else:
        num[j]=k
        k=min(N-1,k+1)
count=0
for i in range(N):
    if L[i][1]>0:
        distance=num[min(L[i][0]+2*D,maximum)]
        for j in range(i,distance+1):
            L[j][1]=L[i][1]-A*math.ceil(L[i][1]/A)
        count+=1
print(count)

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
xh = [list(map(int,input().split())) for _ in range(n)]
x = xh[0][0] + d
ans = 0
b = 0
while b < n:
    while xh[b][1] <= 0:
        if b == n-1:
            break
        b += 1
    for i in range(b ,min(b+ d*2,n)):
        if x - d <= xh[i][0] <= x + d:
            xh[i][1] -= a
    ans += 1
    if xh[-1][0] <= 0:
        break
    x += (xh[b+1][0] - xh[b][0])
       
print(ans)

Submission status: Runtime Error

Solution code:
n, d, a = map(int, input().split())
x = []
h = []
for i in range(n):
    x_, h_ = map(int, input().split())
    x.append(x_)
    h.append(h_)
n_list = range(max(x))

count = 0
j = 0

for i in range(n):
    if x[i] > 0:
        print(h)
        s = x[i]
        bakuha = (h[i]//a)
        h[i] = 0
        count += bakuha
        if i < n-1:
            j = i+1
            while x[j] <= s+(2*d):
                h[j] -= bakuha*a
                if j < n-1:
                    j += 1
                    if h[j] <= 0:
                        h[j] = 0
                        break
                else:
                    break
print(count)

Submission status: Runtime Error

Solution code:
N, D, A = map(int, input().split())
XH = [[0,0] for i in range(N)]
for i in range(N):
    XH[i][0], XH[i][1] = map(int, input().split())
XH.sort()
now = XH[0][0]
i = 0
tmp = 10**9
cnt = 0
while XH[-1][1] > 0:
    tmp = 10**9
    while XH[i][0] <= now + 2 * D:
        if XH[i][1] > 0:
            XH[i][1] -= now
            cnt += 1
        if XH[i][1] > 0:
            tmp = min(tmp, i)
        i += 1
    now = XH[tmp][1]
    i = tmp
print(cnt)