Fişierul intrare/ieşire:gard6.in, gard6.outSursăAlgoritmiada 2018 Runda Finala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.ingard6.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?