Soluții trimise

Rezumat problemă

Se consideră un șir de N numere naturale. O parte dintre poziţiile șirului sunt nevirusate și acest lucru este marcat prin faptul că valoarea de la acele poziţii este 0. Restul poziţiilor sunt virusate și valoarea nenulă de la o poziţie virusată reprezintă costul cu care ea poate fi devirusată. Devirusăm o parte dintre poziţii și dorim ca în final să avem exact K poziţii nevirusate, iar costul total al devirusării să fie minim. O poziţie poate fi devirusată la un moment dat, dacă și numai dacă are cel puţin o poziţie vecină nevirusată. După devirusarea unei poziţii costul asociat acesteia se adună la costul total, poziţia devine nevirusată si orice altă poziţie vecină virusată va putea fi ulterior devirusată.
Cunoscând N, K și șirul de numere naturale să se determine costul minim cu care se pot obţine la final exact K poziţii nevirusate (incluzând şi poziţiile ce au fost iniţial nevirusate).

ONI 2018 clasele XI-XII

ID   Utilizator Problema Data încărcării Stare
Louis Vuitton (LV) antivirus 02 Iulie 2020, 06:47 Evaluare finalizată 100
Yves Saint-Laurent (YSL) antivirus 01 Iulie 2020, 23:43 Evaluare finalizată 100
Marin Alexandru Remus (N4S4Vranci) antivirus 30 Iunie 2020, 15:47 Evaluare finalizată 100
07h3rw1s3 07h3rw1s3 (07h3rw1s3) antivirus 07 Iunie 2020, 11:34 Evaluare finalizată 100
Dumitrescu Ramon (May_9th) antivirus 28 Mai 2020, 19:48 Evaluare finalizată 100
My Chemical Romance Addiction (IustinDodita) antivirus 25 Mai 2020, 12:21 Evaluare finalizată 100
Dragutoiu Vlad (LeVladiator) antivirus 22 Aprilie 2020, 17:48 Evaluare finalizată 100
Dragutoiu Vlad (LeVladiator) antivirus 22 Aprilie 2020, 17:42 Evaluare finalizată 100
Dragutoiu Vlad (LeVladiator) antivirus 22 Aprilie 2020, 17:38 Evaluare finalizată 100
Niţă Mihai-Daniel (nmdaniel) antivirus 17 Aprilie 2020, 18:35 Evaluare finalizată 100
Quintus Maximus (mquintus) antivirus 17 Aprilie 2020, 17:48 Evaluare finalizată 100
Quintus Maximus (mquintus) antivirus 17 Aprilie 2020, 17:48 Evaluare finalizată E.C
Quintus Maximus (mquintus) antivirus 17 Aprilie 2020, 17:42 Evaluare finalizată 50
Quintus Maximus (mquintus) antivirus 17 Aprilie 2020, 17:36 Evaluare finalizată 30
Quintus Maximus (mquintus) antivirus 16 Aprilie 2020, 19:13 Evaluare finalizată 0
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 11:41 Evaluare finalizată 100
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 11:40 Evaluare finalizată 0
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 11:40 Evaluare finalizată 100
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 11:39 Evaluare finalizată 100
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 09:40 Evaluare finalizată 0
Liviu-Constantin Olaru (cplusplus) antivirus 08 Aprilie 2020, 09:40 Evaluare finalizată E.C
Ispir Alexandru (cro) antivirus 07 Aprilie 2020, 16:08 Evaluare finalizată 80
Airinei Andrei Cristian (AirineiAndreiCristian) antivirus 31 Martie 2020, 13:51 Evaluare finalizată 0
abc def (suntprost) antivirus 23 Martie 2020, 11:25 Evaluare finalizată 30
abc def (suntprost) antivirus 23 Martie 2020, 11:25 Evaluare finalizată 30
abc def (suntprost) antivirus 23 Martie 2020, 11:21 Evaluare finalizată 30
abc def (suntprost) antivirus 23 Martie 2020, 11:17 Evaluare finalizată 30
George Andrei (AndreiGe) antivirus 11 Martie 2020, 20:41 Evaluare finalizată 0
Dragan Andrei (dandre1) antivirus 11 Martie 2020, 17:33 Evaluare finalizată 50
Pruteanu Theodor (cyg_Theo) antivirus 04 Martie 2020, 08:52 Evaluare finalizată 100
Bazac Tudor (btudor) antivirus 02 Martie 2020, 14:11 Evaluare finalizată 0
Stoica Alexandru (caesar2001) antivirus 01 Martie 2020, 13:20 Evaluare finalizată 100
Tonitza Nicolae (Nicolae_Tonitza) antivirus 29 Februarie 2020, 14:13 Evaluare finalizată 100
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:58 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:57 Evaluare finalizată 100
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:40 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:40 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:38 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:37 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:32 Evaluare finalizată 30
Teodorescu George (T_george_T) antivirus 17 Februarie 2020, 22:32 Evaluare finalizată 30
Puiu Alexandra (a_puiu) antivirus 13 Februarie 2020, 14:02 Evaluare finalizată 100
C/C++ Java (Nirvana) antivirus 02 Februarie 2020, 16:55 Evaluare finalizată 100
ion popescu (ionpopescuu) antivirus 31 Ianuarie 2020, 23:59 Evaluare finalizată 100
ion popescu (ionpopescuu) antivirus 31 Ianuarie 2020, 23:14 Evaluare finalizată 10
Aldea George Danut (DanutAldea) antivirus 09 Ianuarie 2020, 21:42 Evaluare finalizată 40
Aldea George Danut (DanutAldea) antivirus 09 Ianuarie 2020, 21:33 Evaluare finalizată 80
Aldea George Danut (DanutAldea) antivirus 09 Ianuarie 2020, 21:26 Evaluare finalizată 40
Aldea George Danut (DanutAldea) antivirus 09 Ianuarie 2020, 21:25 Evaluare finalizată 80
Aldea George Danut (DanutAldea) antivirus 09 Ianuarie 2020, 21:24 Evaluare finalizată 30