Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | alpine.in, alpine.out | Sursă | ad-hoc |
|---|---|---|---|
| Autor | Cristian Frâncu | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.07 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
  2.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Alpine (clasele 10-12)
Un hacker își citește e-mailul cu programul Alpine. Pe lângă directorul Inbox, în care intră implicit mesajele primite, el și-a mai definit K directoare (pentru mesajele de la familie, prieteni, serviciu etc.). Venit dintr-o vacanță, hackerul observă că i s-au adunat N mesaje în Inbox. După ce își citește poșta, hackerul dorește să salveze mesajul cu numărul i în directorul Di, pentru 1 ≤ i ≤ N. El caută o metodă cât mai rapidă de a salva mesajele, cu următoarele reguli:
- Poziționează cursorul pe primul mesaj din Inbox.
- Se poate deplasa de la un mesaj la altul, mergând doar în jos (această operație este instantanee).
- Poate salva mesajul curent în directorul său potrivit. Această operație durează T1 secunde.
- Poate adăuga mesajul curent la o selecție. Această operație durează T2 secunde.
- Poate salva toate mesajele selectate în același director. Această operație durează T3 secunde. După salvare, selecția este golită.
- Inițial, selecția este goală.
Date de intrare
Fișierul de intrare alpine.in conține pe prima linie numerele naturale N K T1 T2 T3, cu semnificațiile de mai sus, despărțite prin spații. Pe a doua linie se află numerele naturale D1, D2, ..., DN, despărțite prin spații.
Date de ieșire
În fișierul de ieșire alpine.out se va tipări costul total minim pentru a salva fiecare mesaj în directorul dorit.
Restricții
- 1 ≤ N ≤ 50.000
- 1 ≤ K ≤ 1.000
- 1 ≤ T1, T2, T3 ≤ 10.000
- 1 ≤ Di ≤ K pentru 1 ≤ i ≤ N
Exemplu
| alpine.in | alpine.out |
|---|---|
| 10 4 3 1 4 2 1 2 2 3 4 3 3 3 2 |
24 |
Explicație
Pașii de urmat sunt:
- adaugă mesajul 1 la selecție (cost 1);
- salvează mesajul 2 în directorul 1 (cost 3);
- adaugă mesajul 3 la selecție (cost 1);
- adaugă mesajul 4 la selecție (cost 1);
- salvează selecția (mesajele 1, 3 și 4) în directorul 2 (cost 4);
- adaugă mesajul 5 la selecție (cost 1);
- salvează mesajul 6 în directorul 4 (cost 3);
- adaugă mesajul 7 la selecție (cost 1);
- adaugă mesajul 8 la selecție (cost 1);
- adaugă mesajul 9 la selecție (cost 1);
- salvează selecția (mesajele 5, 7, 8 și 9) în directorul 3 (cost 4);
- salvează mesajul 10 în directorul 2 (cost 3);
Cost total: 24.
