Mastot

from sys import setrecursionlimit
setrecursionlimit(10**6)
 
 
def syöttö():
    etäisyys = int(input())
    kantamasyöte = input().split()
    kantamat = tuple(map(int, kantamasyöte))
    hintasyöte = input().split()
    hinnat = tuple(map(int, hintasyöte))
 
    # Lähetin + Mastot
    mastot = {0: {"kantama": kantamat[0], "hinta": 0}}
    for i in range(etäisyys-1):
        kantama, hinta = kantamat[i+1], hinnat[i]
        mastot[i+1] = {"kantama": kantama, "hinta": hinta}
 
    return mastot, etäisyys
 
 
def pienin_hinta(mastot, etäisyys):
    """
    :param mastot: dic
    :param etäisyys: int
    :return:
    """
    mastotuple = tuple(mastot)
    hinnatmuisti = {}
 
    def seuraavat_mastot(nyt_masto, mastot, etäisyys, hinnatmuisti):
        """
        done: Laita nyt_masto:n hinta muistiin.
        done: Laskee hinnat mukaan
        :param nyt_masto: n:nnes masto
        :param mastot: dic
        :param etäisyys: int
        :param hinnatmuisti: Annetun tolpan halvin hinta siitä eteenpäin.
        :return:
        """
        # Onko muistissa?
        if nyt_masto in hinnatmuisti:
            return hinnatmuisti[nyt_masto]
 
        # Nykyisen maston kantama
        kantama = mastot[nyt_masto]["kantama"]
 
        # Jos kantamaa riittää vastaanottimeen, palautetaan hinta
        if nyt_masto + kantama >= etäisyys:
            hinnatmuisti[nyt_masto] = mastot[nyt_masto]["hinta"]
            return mastot[nyt_masto]["hinta"]
 
        # Tarkista seuraavat mastot
        seuraavista_pienimmät_hinnat = []
        for seuraava_masto in mastotuple[mastotuple.index(nyt_masto) + 1:]:
            # Masto menee kantaman yli
            if nyt_masto + kantama < seuraava_masto:
                break
 
            seuraavista_pienimmät_hinnat.append(
                seuraavat_mastot(seuraava_masto, mastot, etäisyys, hinnatmuisti)
            )
        # min-funktio ottaa kahden tai useamman parametrin
        if len(seuraavista_pienimmät_hinnat) > 1:
            seuraavista_pienin_hinta = min(seuraavista_pienimmät_hinnat)
        # Mastosta ei pääse minnekään
        elif len(seuraavista_pienimmät_hinnat) == 0:
            # Palautetaan jotain tyhmää
            return float("inf")
        else:
            seuraavista_pienin_hinta = seuraavista_pienimmät_hinnat[0]
 
        # Siis nykyisen maston kohdalla hinta on
        # nykyisen_maston_hinta = seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]
        hinnatmuisti[nyt_masto] = seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]
 
        return seuraavista_pienin_hinta + mastot[nyt_masto]["hinta"]
 
        # hinnatmuisti[nyt_masto] = min(seuraavista_pienimmät_hinnat) + mastot[nyt_masto]["hinta"]
        # return min(seuraavista_pienimmät_hinnat) + mastot[nyt_masto]["hinta"]
 
    mastojenhinnat = []
    for läheinen_masto in mastotuple[1:]:
        # Masto menee kantaman yli
        if mastot[0]["kantama"] < läheinen_masto:
            break
        mastojenhinnat.append(seuraavat_mastot(läheinen_masto, mastot, etäisyys, hinnatmuisti))
 
    # if len(mastojenhinnat) > 1:
    return min(mastojenhinnat)
    # else:
    #     return mastojenhinnat[0]
 
 
def poista_turhat_mastot(mastot):
    """
    Poistaa turhat mastot.
    Masto on turha, jos
    1. on olemassa taaempana masto, joka kantaa samaan kohtaan tai pidemmälle
       kuin turha
    2. takana oleva masto ei ole kalliimpi kuin tämä masto
    :param mastot: dict
    """
    # for masto in mastot:
    i = 0
    while True:
        mastotlista = list(mastot)
        masto = mastotlista[i]
 
        # Onko viimeinen masto
        if masto == mastotlista[-1]:
            return
 
        # Mastoja jäljellä
        lähinmasto = mastotlista[mastotlista.index(masto) + 1]
 
        # Monennelleko mastolle täältä pääsee?
        kantama = masto + mastot[masto]["kantama"]
 
        # Tarkastellaan muita mastoja
        for toinenmasto in mastotlista[lähinmasto:]:
            # Onko tämä masto tarkasteltavan maston kantaman reunalla
            # tai sen ulkopuolella
            if kantama <= toinenmasto:
                break
 
            # Onko seuraavan maston kantama huono?
            toisenkantama = toinenmasto + mastot[toinenmasto]["kantama"]
            if kantama >= toisenkantama:
                # Onko se kalliimpi?
                if mastot[toinenmasto]["hinta"] >= mastot[masto]["hinta"]:
                    # Poistetaan tämä
                    del mastot[toinenmasto]
        i += 1
 
 
def main():
    mastot, etäisyys = syöttö()
    # Lähettimen kantama riittää
    if mastot[0]["kantama"] >= etäisyys:
        print(0)
    else:
        poista_turhat_mastot(mastot)
        hinta = pienin_hinta(mastot, etäisyys)
        print(hinta)
 
 
main()

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: RUNTIME ERROR

Traceback (most recent call last):
  File "input/code.py", line 147, in <module>
    main(...

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

Test 12

Group: 1, 2, 3

Verdict: ACCEPTED

Test 13

Group: 1, 2, 3

Verdict: ACCEPTED

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

Test 15

Group: 1, 2, 3

Verdict: ACCEPTED

Test 16

Group: 1, 2, 3

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3

Verdict: ACCEPTED

Test 18

Group: 1, 2, 3

Verdict: ACCEPTED

Test 19

Group: 1, 2, 3

Verdict: ACCEPTED

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

Test 21

Group: 2, 3

Verdict: ACCEPTED

Test 22

Group: 2, 3

Verdict: ACCEPTED

Test 23

Group: 2, 3

Verdict: ACCEPTED

Test 24

Group: 2, 3

Verdict: ACCEPTED

Test 25

Group: 2, 3

Verdict: ACCEPTED

Test 26

Group: 2, 3

Verdict: ACCEPTED

Test 27

Group: 2, 3

Verdict: ACCEPTED

Test 28

Group: 2, 3

Verdict: ACCEPTED

Test 29

Group: 2, 3

Verdict: ACCEPTED

Test 30

Group: 2, 3

Verdict: ACCEPTED

Test 31

Group: 2, 3

Verdict: ACCEPTED

Test 32

Group: 2, 3

Verdict: ACCEPTED

Test 33

Group: 2, 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: ACCEPTED

Test 36

Group: 3

Verdict: ACCEPTED

Test 37

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 3

Verdict: TIME LIMIT EXCEEDED