| Fişierul intrare/ieşire: | waterfront.in, waterfront.out | Sursă | EJOI 2021, ziua 2 |
| Autor | Eugen Nodea | Adăugată de |  Voicu Mihai Valeriu •cadmium_ |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Waterfront
Pe faleza râului Prahova primarul oraşului Ploieşti a plantat un şir de N arbuşti ornamentali de diverse soiuri, fiecare arbust i având iniţial înălţimea height[i], 1 ≤ i ≤ N. În funcţie de solul în care este plantat şi de vreme, arbustul i creşte zilnic cu înălţimea dailyGrowth[i].
În fiecare zi grădinarul primăriei ajustează, prin tăiere cu o foarfecă, înălţimea arbuştilor. Totuşi, grădinarul este limitat de detaliile tehnice ale foarfecii. Astfel, acesta poate tăia la o tăietură exact x centimetri din înălţimea unui arbust dacă înălţimea este cel puţin x (de notat faptul că arbustul poate ajunge la înălţimea 0 după o tăietură). Pentru a nu se obosi, grădinarul poate să efectueze într-o zi cel mult k
tăieturi. Grădinarul poate să efectueze mai multe tăieturi asupra unui arbust într-o zi.
Primarul organizează după M zile un eveniment artistic şi doreşte să aflaţi care este înălţimea minimă a celui mai înalt arbust după cele M zile.
Atenţie! În fiecare zi arbustul întâi creşte şi apoi se fac tăierile
Date de intrare
Fişierul de intrare waterfront.in e conţine pe prima linie numerele naturale N, M, k şi x. Pe următoarele N linii se află câte două numere naturale height[i] şi dailyGrowth[i], separate prin spaţiu.
Date de ieşire
În fişierul de ieşire waterfront.out se va afla un număr nenegativ reprezentând înălţimea minimă a celui mai înalt arbust după cele M zile.
Restricţii
- 1 ≤ k ≤ 1 000
- 1 ≤ x ≤ 10 000
- 1 ≤ height[i] ≤ 10 000
- 1 ≤ dailyGrowth[i] ≤ 10 000
- În plus:
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 8 | N ≤ 100, M = 1, k = 1, x = 1, height[i] ≥ 1, dailyGrowth[i] = 0 |
| 2 | 22 | 1 ≤ N, M ≤ 500 |
| 3 | 43 | 1 ≤ N, M ≤ 5 000 |
| 4 | 27 | 1 ≤ N, M ≤ 10 000 |
Exemplu
| waterfront.in | waterfront.out |
|---|---|
| 4 3 4 3 2 5 3 2 0 4 2 8 | 8 |
Explicaţie
Grădinarul taie arbuştii în 3 zile, în fiecare zi făcând câte 4 tăieturi. La fiecare tăietură poate elimina câte 3 cm din înălţimea arbustului. Următorul tabel ilustrează modul optim de efectuare a tăierilor:
