Fişierul intrare/ieşire:sunmihai.in, sunmihai.outSursăFMI No Stress 9 Warmup
AutorStefan Radu, Usurelu Florian RobertAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sunmihai

Meseria de doctor nu necesita numai cunostinte sau indemanare, ci si inteligenta. Sunmihai, student la "Scoala de Studiu Medical si Farmece" din Lyon (meme 2020), rezolva zilnic jocuri ce dezvolta inteligenta, insa astazi s-a impotmolit. Sunmihai are initial N piese de domino cu cate 2 valori scrise pe ele, in stanga, respectiv in dreapta. O piesa de domino va dobori o alta piesa daca valoarea sa din dreapta esti egala cu valoarea din stanga a piesei ce urmeaza sa fie doborata. Sunmihai are la dispozitie operatii de tip:

  • 1: intoarce piesa de domino cu costul A (valoarile din stanga si dreapta ale piesei se vor interschimba)
  • 2: scoate o piesa oarecare din joc cu costul B (astfel, piesele vecine acesteia vor deveni in relatie; nu se poate aplica aceasta operatie pe prima si ultima piesa de domino)
  • 3: adauga o piesa intre 2 alte piese de domino existente cu costul C (strict dupa prima piesa, dar inaintea ultimei piese; piesa adaugata poate avea valorile din stanga si dreapta orice numere)

Ajutati-l pe Sunmihai si determinati costul minim total astfel incat daca doboram prima piesa, sa cada implicit si ultima (evident, si toate aflate intre prima si ultima).

Date de intrare

Fişierul de intrare sunmihai.in va contine pe prima linie 4 numere N, A, B si C (cu semnificatia din enunt), iar pe fiecare a i-a linie dintre urmatoarele N, cate 2 numere t1 (reprezentand valoarea la stanga a piesei i), respectiv t2 (reprezentand valoarea la dreapta a piesei i).

Date de ieşire

În fişierul de ieşire sunmihai.out se va afla un singur numar reprezentand costul total minim cerut.

Restricţii

  • 1 ≤ N ≤ 100.000 ; 1 ≤ A, B, C ≤ 100 ; 1 ≤ t1, t2 ≤ 100 pentru orice domino
  • Pentru 10 puncte 1 ≤ N ≤ 10 ; 1 ≤ t1, t2 ≤ 5 pentru orice domino
  • Pentru alte 20 puncte 1 ≤ N ≤ 500 ; 1 ≤ t1, t2 ≤ 10 pentru orice domino
  • Pentru alte 20 puncte 1 ≤ N ≤ 5.000 ; 1 ≤ t1, t2 ≤ 50 pentru orice domino
  • Pentru alte 20 puncte 1 ≤ N ≤ 20.000 ; 1 ≤ t1, t2 ≤ 50 pentru orice domino

Exemplu

sunmihai.insunmihai.out
5 8 1 7
2 3
1 1
1 3
3 1
2 1
9

Explicaţie

Scoatem a 2-a si a 3-a piesa cu cost 2 in total si adaugam cu cost 7 o piesa inaintea ultimei piese, avand numarul din stanga 1 si numarul din dreapta 2. In total vom plati 9 unitati, iar dominourile vor arata: (2,3) , (3,1) , (1,2) , (2,1)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?