| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 11 | 3 | 3 | 27.273% |
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.