Mastot

from sys import setrecursionlimit
setrecursionlimit(10**6)


def syöttö():
    etäisyys = int(input())
    kantamasyöte = input().split()
    kantamat = map(int, kantamasyöte)
    hintasyöte = input().split()
    hinnat = map(int, hintasyöte)

    # Lähetin + Mastot
    mastot = {0: {"kantama": next(kantamat), "hinta": 0}}
    for i in range(etäisyys-1):
        kantama, hinta = next(kantamat), next(hinnat)
        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 binäärihaku(lista, haettava):
    """
    Etsii listasta alkion, jonka luku on juuri haettavaa alempi.

    :param lista: Lista lukuja
    :param haettava: Kokonaislukuna haettava kohde
    :return: Haettavan kokonaisluvun alkio
    """
    # Suoritetaan binäärihaku välillä [a,b], missä a ja b ovat listan
    # alkioita
    a = 0
    b = len(lista) - 1

    # Varmistetaan, että haettava on edes listan keskellä
    if haettava <= lista[0]:
        return 0
    if lista[-1] < haettava:
        return len(lista)

    while True:
        keski = (a + b) // 2

        # Onko haettavan ympärillä vain kaksi indeksiä
        if b - a <= 1:
            return b

        # Haettava on välillä [a,keski[
        if haettava <= lista[keski]:
            b = keski
            # print("<-")
        # Haettava on välillä ]keski,b]
        elif lista[keski] < haettava:
            a = keski
            # print("->")


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
    """
    # for masto in mastot:
    masto = 0
    mastoja = len(mastot)
    tarkistettavat_mastot = [(masto + mastot[masto]["kantama"], masto)]
    # Tulee olemaan muotoa [(kantama, masto), (kantama, masto), ...]
    while mastoja - 2 != masto:
        # Seuraava masto
        masto += 1

        kantama = masto + mastot[masto]["kantama"]
        # Ei tarkastella mastoja, joiden kantama ei riitä
        while tarkistettavat_mastot[0][0] <= masto:
            del tarkistettavat_mastot[0]
            # Ei tarkistettavia mastoja
            if len(tarkistettavat_mastot) == 0:
                break

        if tarkistettavat_mastot:
            # Haetaan indeksi
            indeksi = binäärihaku(next(zip(*tarkistettavat_mastot)), kantama)

            # Tarkistetaan, onko tämä masto turha.
            # 1) Maston kantama ei ole paras
            turha = False
            if len(tarkistettavat_mastot) - 1 != indeksi:
                for _, tarkistus_masto in tarkistettavat_mastot[indeksi+1:]:
                    # 2) Maston hinta on korkeampi
                    tämä_masto_hinta = mastot[masto]["hinta"]
                    toinen_masto_hinta = mastot[tarkistus_masto]["hinta"]
                    if tämä_masto_hinta >= toinen_masto_hinta:
                        # Masto on täysin turha
                        del mastot[masto]
                        turha = True
                        break
            if turha:
                continue
        else:
            indeksi = 0

        # Tallennetaan nykyisen maston kantama
        if indeksi == len(tarkistettavat_mastot):
            tarkistettavat_mastot.append((kantama, masto))
        else:
            tarkistettavat_mastot.insert(indeksi, (kantama, masto))


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: ACCEPTED

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