Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
import math
H, N = map(int, input().split())

maho = []
for _ in range(N) :
  A, B = map(int, input().split())
  maho.append([A/B, A, B])
  
maho = sorted(maho, reverse=True)

ans = 0
while H > 0:
  # 1発KOあるかをチェックする
  flag = 0
  for item in maho :
    if item[1] >= H :
      flag = 1
      break
  
  # 1発KOなしの場合
  if flag == 0 :
    cou = int(H/maho[0][1])
    ans += cou*maho[0][2]
    H -= cou*maho[0][1]
  else :
    for item in maho :
      ceil = math.ceil(H/item[1])
      item.insert( 0, ceil*item[2] )
    
    maho = sorted(maho)
    ans += maho[0][0]
    H = -1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

INF = 10**10
def solve(h, n, a, b):
    ab = sorted(zip(a, b), key=lambda _:_[0]/_[1], reverse=True)
    dp = [-1] * h
    def f(h):
        best = INF
        for x, y in ab:
            if h-x <= 0:
                score = y
            else:
                if dp[h-x] == -1:
                    dp[h-x] = f(h-x)
                score = y + dp[h-x]
            if score < best:
                best = score
            else:
                break
        return best
    return f(h)

h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(h, n, a, b))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc153/tasks/abc153_e
# コイン問題の応用で解けそう
# ナップサック解法をあとでちゃんと確認

# INFで初期化したdpテーブルでコイン問題を解いて、ピッタリ勝てないときは最小コストにmin(B)を足す
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, N = read_ints()
A, B = read_col(N, 2)
minb = min(B)
maxa = max(A)
INF = 10**10 + 1

dp = [INF] * (H + 1 + maxa)
dp[0] = 0

for i in range(1, H + 1 + maxa):
    for a, b in zip(A, B):
        if i - a < 0:
            continue
        dp[i] = min(dp[i], dp[i - a] + b)

if dp[H] < INF:
    print(dp[H])
    exit()

print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    ans = inf
    for hp in range(1, h + 1):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)
                if hp >= h:
                    ans = min(ans, dp[hp])

    return ans


main()

Submission status: Wrong Answer

Solution code:
def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    dp = [inf] * (h + 1)
    dp[0] = 0

    # time O(HN)
    max_damage = 0
    for hp in range(1, h + 1):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)
                max_damage = hp

    if max_damage == h:
        return dp[h]
    else:
        min_mp = inf
        for a, m in magic_list:
            if max_damage + a >= h:
                min_mp = min(min_mp, m)
        return dp[max_damage] + min_mp


main()

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
AB = list( list( map(int,input().split()) ) for i in range(N) )
dp = list(range(10**5))
i=0
while i < H or dp[i]==0:
    i += 1
    sumb = []
    for j in range(N):
        if AB[j][0] <= i:
            if AB[j][0] == i or dp[i-AB[j][0]] != 0:
                sumb.append(dp[i-AB[j][0]] + AB[j][1])
    if sumb == []:
        dp[i] = 0
    else:
        dp[i] = min(sumb)
print(dp[i])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
max_a = max(a for a, _ in ab)
dp = [10 ** 18 for _ in range(h + max_a)]
dp[0] = 0
for i in range(1, h + max_a):
    dp[i] = max(dp[i-a] + b for a, b in ab)
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    maxA = max(A)
    HmaxA = H + maxA
    minB = min(B)
    dp = [max(B) * H] * (HmaxA + 1)
    dp[0] = 0
    for h in range(HmaxA):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = h + A[n]
            if hp <= H:
                dp[hp] = min(dp[hp], dp[h] + B[n])
    return min(dp[H:HmaxA+1])

print(ibis(H, A, B))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    minB = min(B)
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + minB)
            hp = h + A[n]
            if hp <= H:
                dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]


dp = [float('inf')] * (H + 1)
def ibis(H):
    min_B = min(B)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            dp[h + 1] = min(dp[h + 1], dp[h] + min_B)
            if h + A[n] <= H:
                dp[h + A[n]] = min(dp[h + A[n]], dp[h] + B[n])
    return dp[H]

print(ibis(H))

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
#print(Magic)
#print(MAX_A)
#print(WORST)
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0],(MAX_A+1)):
#            KARI = []
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
            if j % Magic[i][0] == 0:
                DP[i][j]=min(DP[i][j],((j//Magic[i][0]) * Magic[i][1]))
#            r = j // Magic[i][0]
#            for k in range(r):
#                DP[i][j]=min(DP[i][j],(DP[i-1][j-k*Magic[i][0]]+k*Magic[i][1]))
print(min(DP[N-1][H:MAX_A]))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)*10  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H+max_da):
    if type(dp[i])==int:
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)*2  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        #if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i]+cost[j])

ans=0
for i in range(H,H+max_da):
    if type(dp[i])==int:
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)*2  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H+max_da):
    if type(dp[i])==int:
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
if N==0:
    print(0)
else:
    da, cost = [0] * N, [0] * N
    for i in range(N):
        da[i],cost[i]=map(int, input().split())

    max_da=max(da)  
    dp = [float("inf") for i in range(H+max_da)]
    dp[0]=0

    for j in range(N):
        for i in range(H+max_da):
            if i-da[j]>=0:
                dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

    ans=0
    for i in range(H,H+max_da):
        if type(dp[i])==int:
            ans=dp[i]
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da)  
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H+max_da):
    if type(dp[i])==int:
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
max_da=max(da)  
dp = [float("inf") for i in range(H*100)]
dp[0]=0

for j in range(N):
    for i in range(H*100):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H*100):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
max_da=max(da)  
dp = [float("inf") for i in range(H + max_da)]
dp[0]=0

for j in range(N):
    for i in range(H+max_da):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H+max_da):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())
v=sum(da)  
dp = [float("inf") for i in range(H + v)]
dp[0]=0

for j in range(N):
    for i in range(H+v):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

ans=0
for i in range(H,H+v):
    if dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cos = [0] * N, [0] * N
for i in range(N):
    da[i],cos[i]=map(int, input().split())
v=sum(da)  
dp = [float("inf") for i in range(H + v)]
dp[0]=0

for j in range(N):
    for i in range(H+v):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cos[j])
        dp[i]=dp[i]
ans=0
for i in range(H+v):
    if i>=H and dp[i]!=float("inf"):
        ans=dp[i]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
da, cos = [0] * N, [0] * N
for i in range(N):
    da[i],cos[i]=map(int, input().split())
v=sum(da)  
dp = [[float("inf")] * (H + v) for _ in range(N + 1)]
dp[0][0]=0

for i in range(N):
    for j in range(H+v):
        if j-da[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-da[i]]+cos[i])
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
ans=0
for j in range(H+v):
    if j>=H and dp[N][j]!=float("inf"):
        ans=dp[N][j]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = []
ma = -1
for _ in range(N):
    a, b = map(int, input().split())
    ma = max(ma, a)
    AB.append([a, b])


inf = float('inf')
dp = [inf] * (H + ma + 1)
dp[0] = 0

for h in range(H + 1):
    for a, b in AB:
        dp[h + a] = min(dp[h + a], dp[h] + b)

# print(dp)

for i in range(H, H + ma + 1):
    if dp[i] != inf:
        print(dp[i])
        exit()

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())

attack = []
magic = []
for i in range(n):
    a, b = map(int, input().split())
    attack.append(a)
    magic.append(b)

dp = [[float('inf') for _ in range(h+1)] for _ in range(n+1)]
dp[0][0] = 0
#print(attack, magic)
for i in range(n):
    for j in range(h+1):
        #print(max(dp[i][j], dp[i][j-attack[i]] + magic[i]))
        if dp[i+1][j] > dp[i][j]: dp[i+1][j] = dp[i][j]
        if j-attack[i] >= 0 and dp[i+1][j] > dp[i][j-attack[i]] + magic[i]: dp[i+1][j] = dp[i][j-attack[i]] + magic[i]

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:

h, n = map(int, input().split())

attack = []
magic = []
for i in range(n):
    a, b = map(int, input().split())
    attack.append(a)
    magic.append(b)

dp = [[float('inf') for _ in range(h+1)] for _ in range(n+1)]
dp[0][0] = 0
#print(attack, magic)
for i in range(n):
    for j in range(h+1):
        #print(max(dp[i][j], dp[i][j-attack[i]] + magic[i]))
        if dp[i+1][j] > dp[i][j]: dp[i+1][j] = dp[i][j]
        if j-attack[i] >= 0 and dp[i+1][j] > dp[i][j-attack[i]] + magic[i]: dp[i+1][j] = dp[i][j-attack[i]] + magic[i]

print(dp)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A_B_DPM = []
for _ in range(N):
  A, B = map(int, input().split())
  A_B_DPM.append([A, B, A/B])

DPM_First = sorted(A_B_DPM, reverse=True, key=lambda x: (x[2], -x[1]))
damage_sort = sorted(A_B_DPM, key=lambda x: x[0])
ans = 0
flag = False
while H > 0:
  if H - DPM_First[0][0] < 0:
    n = len(damage_sort)
    for i in range(N):
      if damage_sort[i][0] > H:
        for _ in range(n - i - 1):
          damage_sort.pop(-1)
        break
    DPM_First = sorted(damage_sort, reverse=True, key=lambda x: (x[2], -x[1]))
  H -= DPM_First[0][0]
  ans += DPM_First[0][1]
print(ans)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
ma=max(a for a,b in A)
dp=[0]*(h+ma)
for i in range(h+ma):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
dp=[10**9]*(h+10010)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for i in range(h+10010):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
dp=[0]*(h+10010)
A=[list(map(int,input().split())) for i in range(n)]
dp[0]=0
for i in range(h+10010):
  dp[i]=min(dp[i-a]+b for a,b in A)
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]= map(int,input().split())

maxi=max(A)
DP=[0]*(H+maxi)
DP[0]=0

for i in range(1,H+maxi):
  mini=10000000
  for j in range(N):
    if i-A[j]>=0:
      mini=min(mini, DP[i-A[j]]+B[j])
  DP[i]=mini
  
mini2=1000000000
for k in range(H,H+maxi):
  mini2=min(mini2,DP[k])

print(mini2)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
A=[0]*N
B=[0]*N
for i in range(N):
  A[i],B[i]= map(int,input().split())

DP=[0]*(H+1)
DP[0]=0

for i in range(1,H+1):
  mini=100000
  for j in range(N):
    if i-A[j]>=0:
      mini=min(mini, DP[i-A[j]]+B[j])
  if mini<100000:
    DP[i]=mini
  else:
    DP[i]=DP[i-1]
  
print(DP)

Submission status: Wrong Answer

Solution code:
import sys

class Magic:
  def __init__(self, damage, cost):
    self.damage = damage
    self.cost = cost
    
  def cost_at(self, damage):
    return (damage + self.damage - 1) // self.damage * self.cost

H, N = map(int, input().split())

magics = []

for _ in range(N):
  a, b = map(int, input().split())
  magics.append(Magic(a, b))
  
max_damage = max(m.damage for m in magics)
  
memo = [[sys.maxsize] * (H + max_damage) for _ in range(N)]

for i in range(N):
  for h in range(1, H + max_damage):
    # 初期化
    if i == 0:
      memo[i][h] = magics[i].cost_at(h)
    else:
      memo[i][h] = min(
        memo[i - 1][h],
        memo[i][h - magics[i].damage] + magics[i].cost
      )
  
print(min(memo[N - 1][H:]))

Submission status: Wrong Answer

Solution code:
import numpy as np

h, n = map(int, input().split())
ab = np.array([list(map(int, input().split()))])

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(dp[h])

Submission status: Wrong Answer

Solution code:
import numpy as np

h, n = map(int, input().split())
ab = np.array([list(map(int, input().split()))])

a, b = ab[:, 0], ab[:, 1]
dp = np.zeros(h+1, dtype=np.int)
for i in range(1, h+1):
    dp[i] = np.min(dp[np.maximum(i-a, 0)] + b)

print(dp[h])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
l = []
for i in range(n):
  a, b = map(int, input().split())
  l.append([a, b])

dp = [10 ** 8 + 1 for i in range(h + 10**4 + 1)]
dp[0] = 0

for i in range(h+1):
  for j in range(n):
    if dp[i] == 10 ** 8 + 1:
      continue

    x = dp[i] + l[j][1]
    if dp[i + l[j][0]] > x:
      dp[i + l[j][0]] = x

print(dp[h])

Submission status: Wrong Answer

Solution code:
H,N= map(int,(input().split()))
mag = [[0] * 3 for j in range(N)]
use=0
for i in range(N):
  mag[i][0],mag[i][1]=map(int,(input().split()))
  mag[i][2]=mag[i][0]/mag[i][1]
mag.sort(key=lambda x:(x[2],x[0]))
#print(mag)
while(H>0):
  if(H>=mag[N-1][0] or len(mag)==1 ):
    H-=mag[N-1][0]
    use+=mag[N-1][1]
    #print("上")
  else:
    del mag[-1:]
    N-=1
    #print("下")
print(use)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)

h,n=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
AB = [tuple(map(int, input().split())) for _ in range(n)]
#効率順にソート
AB.sort(key=lambda ab: (ab[1] / ab[0], ab[0]))

@lru_cache(maxsize=None)
def dp(h):
    if h <= 0:
        return 0
    else:
        best = float('inf')
        print(h)
        for a, b in AB:
            mp = b + dp(h -a)
            if mp < best:
                best = mp
            else:
                break
        return best

print(dp(h))

Submission status: Wrong Answer

Solution code:
H,N= map(int,(input().split()))
mag = [[0] * 3 for j in range(N)]
use=0
for i in range(N):
  mag[i][0],mag[i][1]=map(int,(input().split()))
  mag[i][2]=mag[i][0]/mag[i][1]
mag.sort(key=lambda x:(x[2],x[0]))

while(H>0):
  if(H>mag[N-1][0] or len(mag)==1 ):
    H-=mag[N-1][0]
    use+=mag[N-1][1]

  else:
    del mag[-1:]
    N-=1

print(use)

Submission status: Wrong Answer

Solution code:
import math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B
    
    minA=min(dp[H-A:])+B
    if minA < dp[-1]:
        dp[-1]=minA

print(dp[-1])

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
L = []
for i in range(n):
  l = list(map(int,input().split()))
  L.append(l)
dp = [10**8]*10001
dp[0] = 0
for i in range(n):
  dp[L[i][0]] = L[i][1]
for i in range(10001):
  for j in range(n):
    if i-L[j][0] >= 0:
      dp[i] = min(dp[i],dp[i-L[j][0]]+L[j][1])
for i in range(9999,-1,-1):
  if dp[i] == 10**8:
    dp[i] = dp[i+1]
print(dp[h])

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
L = []
for i in range(n):
  l = list(map(int,input().split()))
  L.append(l)
dp = [float('inf')]*10001
dp[0] = 0
for i in range(n):
  dp[L[i][0]] = L[i][1]
for i in range(10001):
  for j in range(n):
    if i-L[j][0] >= 0:
      dp[i] = min(dp[i],dp[i-L[j][0]]+L[j][1])
for i in range(9999,-1,-1):
  if dp[i] == float('inf'):
    dp[i] = dp[i+1]
print(dp[h])

Submission status: Wrong Answer

Solution code:
import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B
        print(dp)

    print(dp[-1])

main()

Submission status: Wrong Answer

Solution code:
import math
import copy
H,N=map(int,input().split())

inf=float('inf')
dp=[0]+[inf]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    dp=ndp
    if A>=H:
        ndp[-1]=min(B,dp[-1])

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math
import copy
H,N=map(int,input().split())

inf=float('inf')
dp=[0]+[inf]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=copy.deepcopy(dp)
    for j in range(A,H+1):
        ndp[j]=min(ndp[j-A]+B,dp[j])

        if j > H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

    dp=ndp

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math
import copy
H,N=map(int,input().split())

dp=[0]+[None]*H

for i in range(N):
    A,B=map(int,input().split())
    ndp=[0]+[None]*H
    for j in range(A,H+1):
        if dp[j]==None:
            if ndp[j-A]!=None:
                ndp[j]=ndp[j-A]+B
            continue
        
        if ndp[j-A]==None:
            if dp[j]!=None:
                ndp[j]=dp[j]
            
            continue

        if ndp[-1]==None:
            pass
        elif j >=H-A:
            ndp[-1]=min(ndp[-1],ndp[j]+B)

        ndp[j]=min(ndp[j-A]+B,dp[j])

    if A >= H and dp[-1]!=None:
        ndp[-1]=min(B,dp[-1])

    dp=ndp

print(dp[-1])

Submission status: Wrong Answer

Solution code:
h, n = list(map(int, input().split()))

damage = [0] * n
mp     = [0] * n
for i in range(n):
    damage[i], mp[i] = list(map(int, input().split()))


inf = 9999999999
# dp[i][j]: i番目までの魔法からダメージの総和がjになる最小のMP
dp = [[inf] * (h+1) for i in range(n+1)]


for i in range(n):
    for j in range(h+1):
        if(i == 0 and damage[0] >= j):
            dp[i][j] = mp[0]
        if(j == 0):
            dp[i][j] = 0

        if(j < damage[i]):
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-damage[i]] + mp[i])

print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys


def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == 'main':
    print(resolve())

Submission status: Wrong Answer

Solution code:



def resolve():
    H, N = map(int, sys.stdin.readline().split())
    m = map(int, sys.stdin.read().split())
    AB = zip(m, m)
    INF = 10**20
    dp = [INF]*(H+10**4)
    dp[0] = 0
    for a, b in AB:
        for j in range(H+10**4):
            dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
    return min(dp[H:])


if __name__ == 'main':
    print(resolve())

Submission status: Wrong Answer

Solution code:
hp, count = map(int, input().split())
at_list = []
for _ in range(count):
	at, mp = map(int, input().split())
	at_list.append({'at': at, 'mp': mp})	
	
mi_mp = 100000000000001
all_mp_count = 0

while hp > 0:
	for atl in at_list:
		if mi_mp > (hp // atl['at'] + 1) * atl['mp']:
			attack =  atl['at']
			mp_count = atl['mp']
			mi_mp = (hp // atl['at'] + 1) * atl['mp']
	hp -= attack
	all_mp_count += mp_count
	mi_mp = 100000000000001
print(all_mp_count)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N=map(int,input().split())
A=np.empty(N)
B=np.empty(N)
for i in range(N):
	x,y=map(int,input().split())
	A[i]=x
	B[i]=y
C=A-B
count=0
while True:
	if (H-np.max(C))>0:
		H=H-A[np.argmax(C)]
		count+=B[np.argmax(C)]
		continue
	elif (H-np.max(C))<=0 and C.shape[0]!=1:
		C=np.delete(C,obj=np.argmax(C))
		B=np.delete(B,obj=np.argmax(C))
		continue
	elif (H-np.max(C))<=0 and C.shape[0]==1:
		count+=B[0]
		break

print(int(count))

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
A,B=[],[]
for i in range(n):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)
dp = [0]*(h+1)
for i in range(1,h+1):
  M = 10**6
  for j in range(n):
    check = max(0,i-A[j])
    M = min(M,dp[check]+B[j])
  dp[i] = M
print(dp[h])

Submission status: Wrong Answer

Solution code:
import math
h,n = map(int,input().split())


ab = []
for i in range(n):
    ab.append([int(i) for i in input().split()])
ab.sort()
dp = []
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    if i == 0:
        for j in range(h):
            dp.append(math.ceil((j + 1) / a) * b)
    for j in range(a, h):
        if j - a >= 0:
            if dp[j] > dp[j - a] + b:
                dp[j] = dp[j - a] + b

print(dp[h - 1])

Submission status: Wrong Answer

Solution code:
# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    dp = [float("inf")] * (W + 1)
    dp[0] = 0
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]
        w = ws[i]
        for j in range(w, W + 1):
            dp[j] = min(dp[j - w] + v, dp[j])
    return dp


h, n = map(int, input().split())

ws = []
vs = []
for _ in range(n):
    a, b = map(int, input().split())
    ws.append(a)
    vs.append(b)

dp = solve(n, 2*h, ws, vs)

print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
# i番目の重みws[i], 価値vs[i]
def solve(N, W, ws, vs):
    dp = [0] * (W + 1)
    for i in range(N):
        # 価値v, 重さw
        v = vs[i]
        w = ws[i]
        for j in range(w, W + 1):
            dp[j] = max(dp[j - w] + v, dp[j])
    return dp


h, n = map(int, input().split())

ws = []
vs = []
for _ in range(n):
    a, b = map(int, input().split())
    ws.append(a)
    vs.append(b)

dp = solve(n, 2*h, ws, vs)

print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n = input().split()
h = int(h)
s =[]
m = 0
for i in range(int(n)):
    a = input().split()
    a = [int(i) for i in a]
    a.append(a[0]/a[1])
    s.append(a)

#print(s)
s.sort(key=lambda s:(s[2], s[0]), reverse=True)
#print(s)

while h >= s[0][0]:
	h = h -s[0][0]
	m = m +s[0][1]

#print(s[0][0])
#print(h)
#print(m)

slim=[i for i in s if i[2] <= s[0][2]]
slim.sort(key=lambda s:(s[1], s[0]))
#print(slim)

while h >0:
	h = h -slim[0][0]
	m = m +slim[0][1]
#print(h)
print(m)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
A=[]
B=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
#dp[i]=x  ダメージi与えるのに必要な魔力x　答えはdp[h]
INF=10**10
dp=[INF]*(10**5+5)
dp[0]=0
for i in range(h+1):
  m=dp[i]
  for j in range(n):
    if i-A[j]<0:
      continue
    a=dp[i-A[j]]+B[j]
    if a<m:
      m=a
  dp[i]=m
  for j in range(i+1,i+1-min(A)-3,-1):
    if dp[j]>dp[j+1]:
      dp[j]=dp[j+1]
print(dp[h])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
A=[]
B=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
#dp[i]=x  ダメージi与えるのに必要な魔力x　答えはdp[h]
INF=10**10
dp=[INF]*(10**5+5)
dp[0]=0
for i in range(n):
  dp[A[i]]=B[i]
for i in range(max(A)+1,0,-1):
  if dp[i]==INF:
    dp[i]=dp[i+1]
for i in range(min(A),h+1):
  m=dp[i]
  for j in range(n):
    if i-A[j]<0:
      continue
    a=dp[i-A[j]]+B[j]
    if a<m:
      m=a
  dp[i]=m
print(dp[h])

Submission status: Wrong Answer

Solution code:
H, N = (int(i) for i in input().split())
A = []
B = []
for i in range(N):
    a, b = (int(j) for j in input().split())
    A.append(a)
    B.append(b)
A_max = max(A)

DP = [0]
for i in range(1, H+A_max):
    dp = H*A_max
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP.append(dp)
print(min(DP[H:]))

Submission status: Wrong Answer

Solution code:
H, N = (int(i) for i in input().split())
A = []
B = []
for i in range(N):
    a, b = (int(j) for j in input().split())
    A.append(a)
    B.append(b)
A_max = max(A)

DP = [0]
for i in range(1, H+A_max):
    dp = 10000
    for a, b in zip(A,B):
        if i-a>=0:
            dp = min(dp, DP[i-a] + b)
    DP.append(dp)
print(min(DP[H:]))