Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | gard6.in, gard6.out | Sursă | Algoritmiada 2018 Runda Finala |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gard6
Tanaka, rezident al satucului Şuieb, a fost surprins de faptul că, în faţa casei sale s-au construit peste noapte N blocuri adiacente de lăţime egală, şi de diverse înălţimi non-negative. Cum acestea i-au blocat vederea la plaiul mioritic, el a hotărât să construiască un gard astfel încât să nu mai vadă blocurile respective.
Tanaka va construi gardul din K scânduri dreptunghiulare. O scândură se consideră a acoperi o subsecvenţă de blocuri consecutive dacă ea are o înălţime mai mare sau egala cu cea a tuturor blocurile din subsecvenţă, şi o lăţime egală cu numărul de blocuri din secvenţă.
Dorind să economisească banii, Tanaka ar vrea să ştie care ar fi aria totală minimă de lemn necesară pentru a acoperi toate blocurile cu K scanduri.
Date de intrare
Pe prima linie a fişierului gard6.in se vor găsi N şi K.
Pe a doua linie se vor găsi înălţimile blocurilor, de la stânga la dreapta.
Date de ieşire
Singura linie a fişierului gard6.out va conţine aria minimă necesară.
Precizări şi restricţii
- 1 ≤ K ≤ N ≤ 100 000
- N * K ≤ 250 000
- Inaltimile blocurilor nu depasesc 1 000 000 000 (Şuiebul este totusi doar un sătuc, nu are blocuri inalte).
- Blocuri de inaltime 0 trebuie acoperite si ele de scanduri, cu putinta de inaltime 0.
- Interiorurile scandurilor nu se pot intersecta.
- Pentru 19 puncte, N2 * K ≤ 1 000 000
- Pentru alte 32 puncte, N * K ≤ 75 000 si inaltimile blocurilor nu depasesc 20.
- Pentru alte 24 puncte, N * K ≤ 75 000 si sirul de valori este generat aleator.
- Pentru alte 10 puncte, N * K ≤ 150 000.
Exemplu
| gard6.in | gard6.out |
|---|---|
| 4 2 1 2 3 4 | 12 |
| 5 2 2 4 0 2 4 | 18 |
| 10 3 910 884 805 589 529 436 427 291 46 13 | 5767 |
Explicaţie
In primul exemplu, aria totală de 12 unităţi se poate realiza cu o scăndură lată de 2 unităţi şi înaltă de 2, urmată de o scândură lată de 2 unitati şi înaltă de 4.
In cel de-al doilea exemplu, aria totala de 18 unitati se poate realiza cu o scandura lata de 1 unitate si inalta de 2 unitati, urmata de o scandura lata de 4 unitati si inalta de 4 unitati.
