Code Submission Evaluation System Login

Datatähti 2020 alku

Start:2019-09-30 00:00:00
End:2019-10-14 00:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2020 alku - MastotCSES - Mastot

Mastot

Time limit:1.00 s
Memory limit:512 MB

Haluat muodostaa radioyhteyden etäisyyden $n$ päässä olevaan vastaanottimeen. Radiolähettimesi kantama ei kuitenkaan välttämättä riitä, ja voit joutua välittämään signaalin mastojen kautta.

Lähettimen ja vastaanottimen välissä on tasavälein $n-1$ mastoa etäisyyksillä $1, 2, \dots, n-1$ lähettimestä. Mastot lähettävät edelleen vastaanottamansa signaalit. Lähettimellä ja kullakin mastolla on kantama $d_i$, joka kuvaa molempiin suuntiin suurinta etäisyyttä, jolla kyseisestä paikasta lähetetyn signaalin voi vastaanottaa.

Kaikki mastot ovat kuitenkin epäkunnossa, ja maston $i$ korjaamisen hinta on $c_i$.

Mikä on pienin kokonaishinta, jolla saat vastaanottimeen yhteyden?

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku $n$: vastaanottimen etäisyys.

Toisella rivillä on $n$ kokonaislukua $d_0, d_1, ..., d_{n-1}$: lähettimen kantama ja mastojen kantamat.

Kolmannella rivillä on $n-1$ kokonaislukua $c_1, ..., c_{n-1}$: mastojen korjauksien hinnat.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kokonaishinta.

Esimerkki

Syöte:
6
2 2 3 1 2 4
4 1 3 4 2


Tuloste:
3

Selitys: Optimaalinen ratkaisu on korjata mastot etäisyyksillä $2$ ja $5$.

Kaikissa osatehtävissä pätee $1 \leq d_i \leq n$ ja $1 \leq c_i \leq 10^9$.

Osatehtävä 1 (11 pistettä)
Osatehtävä 2 (34 pistettä)
Osatehtävä 3 (55 pistettä)