Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Laudat


Task | Statistics


CSES - LaudatCSES - Laudat

Time limit:1.00 s Memory limit:512 MB

Sinulla on lauta, jonka pituus on $x$. Haluat jakaa sen $n$ laudaksi, joiden pituudet ovat $p_1,p_2,\ldots,p_n$.

Jokaisella vuorolla voit valita minkä tahansa laudan ja jakaa sen kahteen osaan haluamallasi tavalla. Tällaisen jaon kustannus on laudan pituus ennen jakoa.

Mikä on pienin mahdollinen kaikkien kustannusten summa?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $x$ ja $n$: alkuperäisen laudan pituus ja haluttujen lautojen määrä.

Seuraavalla rivillä on $n$ kokonaislukua $p_1,p_2,\ldots,p_n$: halutut pituudet.

Tuloste

Tulosta yksi kokonaisluku: pienin kokonaiskustannus.

Rajat
Esimerkki

Syöte:
8 3
2 3 3


Tuloste:
13

Selitys: Alussa laudat ovat $[8]$. Jaat $8$:n pituisen laudan osiin $3+5=8$ (kustannus $8$), minkä jälkeen laudat ovat $[3,5]$. Sitten jaat $5$:n pituisen laudan osiin $2+3=5$ (kustannus $5$), minkä jälkeen laudat ovat $[2,3,3]$.