Submission #3820190

---

Source Code Expand

# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

# リスト入力
D, G = map(int, input().split())
d = []
for i in range(D):
    x, y = map(int, input().split())   
    d.append((x, y))
q = []
mem = defaultdict(lambda:defaultdict(int))
heapq.heappush(q, (0, 0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]))

while(q):
    su, v, l = heapq.heappop(q)
    for i in range(D):
        vi = -v
        li = list(l)
        if (li[i] < d[i][0]):
            li[i] += 1
            vi += (i + 1) * 100
            if (mem[vi][sum(li)] == 1):
                continue
            if (li[i] == d[i][0]):
                vi += d[i][1]
            if (vi >= G):
                print(sum(li))
                sys.exit()
            else:
                heapq.heappush(q, (sum(li), -vi, li))
                mem[vi][sum(li)] = 1

Submission Info

Judge Result