#1199
Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.
Se dă planul unei rețele de metrou cu N stații și M tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i are asociat un profit p[i] dat.
Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.
Dându-se N, M, profiturile aduse de fiecare din cele N stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.
ONI 2015, Clasele XI-XII
| ID | Utilizator | Problema | Data încărcării | Stare | ||
|---|---|---|---|---|---|---|
| Metrou | 16 Mai 2026, 11:23 | Evaluare finalizată | 20 | |||
| Metrou | 23 Martie 2026, 23:49 | Evaluare finalizată | 70 | |||
| Metrou | 23 Martie 2026, 23:47 | Evaluare finalizată | 100 | |||
| Metrou | 23 Martie 2026, 23:38 | Evaluare finalizată | 10 | |||
| Metrou | 22 Martie 2026, 18:42 | Evaluare finalizată | 100 | |||
| Metrou | 20 Martie 2026, 20:57 | Evaluare finalizată | 100 | |||
| Metrou | 20 Martie 2026, 20:50 | Evaluare finalizată | 40 | |||
| Metrou | 18 Martie 2026, 10:36 | Evaluare finalizată | 20 | |||
| Metrou | 12 Martie 2026, 14:14 | Evaluare finalizată | 100 | |||
| Metrou | 12 Martie 2026, 14:14 | Evaluare finalizată | 100 | |||
| Metrou | 28 Februarie 2026, 17:37 | Evaluare finalizată | 10 | |||
| Metrou | 04 Februarie 2026, 13:34 | Evaluare finalizată | E.C | |||
| Metrou | 24 Ianuarie 2026, 12:41 | Evaluare finalizată | 100 | |||
| Metrou | 20 Ianuarie 2026, 09:09 | Evaluare finalizată | 20 | |||
| Metrou | 19 Ianuarie 2026, 02:11 | Evaluare finalizată | 0 | |||
| Metrou | 18 Decembrie 2025, 14:07 | Evaluare finalizată | E.C | |||
| Metrou | 08 Noiembrie 2025, 01:47 | Evaluare finalizată | 100 | |||
| Metrou | 23 Octombrie 2025, 19:19 | Evaluare finalizată | 100 | |||
| Metrou | 23 Octombrie 2025, 19:16 | Evaluare finalizată | 90 | |||
| Metrou | 23 Octombrie 2025, 19:08 | Evaluare finalizată | 0 | |||
| Metrou | 23 Octombrie 2025, 19:08 | Evaluare finalizată | 10 | |||
| Metrou | 23 Octombrie 2025, 18:26 | Evaluare finalizată | 90 | |||
| Metrou | 23 Octombrie 2025, 18:23 | Evaluare finalizată | 90 | |||
| Metrou | 23 Octombrie 2025, 18:21 | Evaluare finalizată | 60 | |||
| Metrou | 23 Octombrie 2025, 18:20 | Evaluare finalizată | 90 | |||
| Metrou | 23 Octombrie 2025, 18:20 | Evaluare finalizată | 70 | |||
| Metrou | 23 Octombrie 2025, 17:59 | Evaluare finalizată | 50 | |||
| Metrou | 23 Octombrie 2025, 17:58 | Evaluare finalizată | 0 | |||
| Metrou | 23 Octombrie 2025, 17:58 | Evaluare finalizată | 70 | |||
| Metrou | 23 Octombrie 2025, 17:42 | Evaluare finalizată | 70 | |||
| Metrou | 06 August 2025, 00:09 | Evaluare finalizată | 100 | |||
| Metrou | 06 August 2025, 00:03 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:59 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:56 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:54 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:46 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:40 | Evaluare finalizată | 90 | |||
| Metrou | 05 August 2025, 23:35 | Evaluare finalizată | 70 | |||
| Metrou | 05 August 2025, 23:31 | Evaluare finalizată | 20 | |||
| Metrou | 05 August 2025, 23:27 | Evaluare finalizată | E.C | |||
| Metrou | 05 August 2025, 23:23 | Evaluare finalizată | 50 | |||
| Metrou | 05 August 2025, 23:23 | Evaluare finalizată | 40 | |||
| Metrou | 04 August 2025, 17:32 | Evaluare finalizată | 20 | |||
| Metrou | 12 Aprilie 2025, 23:29 | Evaluare finalizată | E.C | |||
| Metrou | 02 Aprilie 2025, 15:07 | Evaluare finalizată | 0 | |||
| Metrou | 12 Martie 2025, 16:00 | Evaluare finalizată | 0 | |||
| Metrou | 12 Martie 2025, 15:55 | Evaluare finalizată | 0 | |||
| Metrou | 06 Martie 2025, 19:34 | Evaluare finalizată | 0 | |||
| Metrou | 05 Martie 2025, 08:11 | Evaluare finalizată | 0 | |||
| Metrou | 04 Martie 2025, 22:52 | Evaluare finalizată | E.C | |||