Fişierul intrare/ieşire:hypernet.in, hypernet.outSursăSummer Challenge 2007, runda 2
AutorMugurel Ionut AndreicaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hypernet

In galaxia noastra exista N planete, numerotate de la 1 la N. Fiecare planeta are un anumit numar de locuitori (planeta i are Qi locuitori). Guvernul galaxiei doreste sa construiasca o retea compusa din K hipercanale (canale de transport prin hiperspatiu) bidirectionale, fiecare hipercanal conectand 2 planete distincte. Folosind reteaua construita, fiecare locuitor al fiecarei planete va dori sa viziteze fiecare din celelalte planete. Costul transportului printr-un hipercanal este de 1 unitate monetare pentru orice locuitor al oricarei planete. Prin urmare, costul vizitarii planetei j de catre un locuitor al planetei i este egal cu numarul minim de hipercanale ce trebuie traversate pentru a ajunge de la planeta i la planeta j (vom numi acest numar disti,j). Costul total al retelei de hipercanale este egal cu suma costurilor platite de fiecare locuitor al fiecarei planete:

Cerinta

Determinati costul total minim al unei retele constand din K hipercanale.

Date de intrare

Prima linie a fisierului de intrare hypernet.in contine 2 numere intregi, separate printr-un spatiu: N si K. A i-a din urmatoarele N linii contine numarul intreg Qi, reprezentand numarul de locuitori ai planetei i.

Date de iesire

In fisierul de iesire hypernet.out afisati costul total minim al unei retele de hipercanale avand proprietatile specificate.

Restrictii

  • 1 ≤ N ≤ 50.000
  • N-1 ≤ K ≤ N*(N-1)/2
  • 1 ≤ Qi ≤ 1.000.000

Exemplu

hypernet.inhypernet.out
4 3
4
3
1
2
42
4 5
10
9
8
7
117
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content