Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-04-09 11:18:03.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:spiridusi.in, spiridusi.outSursăONI 2015 Clasele 11-12
AutorVlad GavrilaAdăugată deassa98Andrei Stanciu assa98
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Spiridusi

Mei şi Satsuki s-au întors de curând în casa de vacanţă a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s i spiriduşi de praf.
Cele două fete doresc să-şi amenajeze un spaţiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a şi b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeaşi cameră), gonind spiriduşii de praf aflaţi în fiecare cameră prin care trec, inclusiv pe cei din camerele a şi b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiriduşii de praf au fost alese pentru spaţiul de joacă.
Fetele au stabilit pentru fiecare cameră i un coeficient p i care reprezintă cât de plăcută ar fi camera i pentru spaţiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduşi ai prafului din camerele prin care trec.

Cerinta

Cunoscând valorile lui N şi C, numărul de spiriduşi ai prafului s i , coeficienţii p i pentru fiecare cameră i, cât şi modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienţilor p ai camerelor alese pentru un spaţiu de joacă ce respectă condiţiile impuse de Mei şi Satsuki.

Date de intrare

Pe prima linie a fişierului de intrare spiridusi.in se vor afla două numere naturale N şi C cu semnificaţia din enunţ. Pe a doua linie se vor afla N numere naturale separate prin câte un spaţiu, al i-lea dintre acestea reprezentând numărul de spiriduşi s i aflaţi în camera i. Pe a treia linie se vor afla N numere întregi separate prin câte un spaţiu, al i-lea dintre acestea reprezentând coeficientul p i al camerei i. Pe următoarele N-1 linii se vor afla câte două numere întregi x şi y separate printr-un spaţiu, semnificând existenţa unui culoar ce uneşte camerele x şi y.

Date de ieşire

În fişierul de ieşire spiridusi.out ...

Restricţii

  • ... ≤ ... ≤ ...

Exemplu

spiridusi.inspiridusi.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?