| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 13 | 5 | 5 | 38.462% |
Bliže se lokalni izbori!
Prije promjene vlasti potrebno je podijeliti bonuse u jednom neimenovanom odjelu gradske uprave. Hijerarhiju uprave možemo predstaviti stablom u kojem je čvor $1$ označen kao direktor, a izravni šef svakog zaposlenika je njegov roditelj u stablu.
Ako $i$-ti zaposlenik dobije bonus u iznosu od barem $c_i$, njegova će se produktivnost u sljedećoj godini povećati za $p_i$, dok u suprotnom ostaje nepromijenjena. Nije nužno da svi zaposlenici dobiju bonus, ali za svakog zaposlenika koji dobije bonus mora vrijediti da je i njegov izravni šef dobio barem neki pozitivan bonus (makar u iznosu $1$).
Odredite najveće moguće povećanje ukupne produktivnosti odjela ako je ukupan iznos proračuna za bonuse najviše $K$.
U prvom retku su prirodni brojevi $N$ i $K$.
U drugom je retku $N − 1$ brojeva $s_i$ ($1 ≤ s_i ≤ i$) gdje $i$-ti broj označava izravnog šefa $i + 1$-tog radnika.
U trećem je retku $N$ brojeva $p_1, p_2, \dots , p_N$.
U četvrtom je retku $N$ brojeva $c_1, c_2, \dots , c_N$.
U jedini redak ispišite najveće moguće povećanje produktivnosti uz zadani proračun.
U svim podzadacima vrijedi $2 ≤ N ≤ 5\, 000$ i $1 ≤ K ≤ 5\, 000$.
Za sve $i = 1, \dots , N$ vrijedi da je $1 ≤ p_i ≤ 10^5$ i $1 ≤ c_i ≤ 5\, 000$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N ≤ 20$ |
| 2 | 9 | $c_i = 1$ za sve $i$ i dodatno ako je $j$ šef od $i$ tada $p_j ≥ p_i$. |
| 3 | 14 | Za sve $i < N$, izravan šef od $i + 1$ je $i$. |
| 4 | 19 | $N, K ≤ 500$ |
| 5 | 21 | $N ≤ 100$ |
| 6 | 30 | Nema dodatnih ograničenja. |
2 100 1 10 10 101 100
0
5 7 1 1 2 2 2 1 2 3 3 4 2 4 2 3
6
4 9 1 2 2 3 4 4 2 2 5 5 4
7
Pojašnjenje drugog probnog primjera:
Primjer valjane dodjele bonusa je sljedeći: zaposlenici dobiju redom $1$, $1$, $0$, $2$ i $3$ bonusa.
Dodjela $1$, $1$, $1$, $2$, $3$ nije valjana jer ukupni broj dodijeljenih bonusa premašuje dozvoljeni proračun.
Dodjela $0$, $1$, $1$, $2$, $3$ također nije valjana jer je zaposlenik $2$ dobio bonus, a njegov izravni šef nije.