Arpsod are în curtea sa N copaci foarte bătrâni, așezați în linie și numerotați de la 1 la N. Fiecare copac are o înălțime cunoscută, H_i. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni.

Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea 1, 2, 3, ... ,N iar cel de-al doilea în ordinea N, N-1, N-2, ... 1.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul 1 are un tarif de T1 pe metru iar muncitorul 2 un tarif de T2 pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar C pentru a rămâne să taie în continuare.

De exemplu, dacă avem 3 copaci: 1, 2, 3 și muncitorul 1 taie singur toți copacii, acesta va cere un cost suplimentar de 2 ori (pentru copacul 2 și copacul 3).

Cerința

Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei N copaci să fie tăiați.

Date de intrare

Pe prima linie a fișierului democratie.in se va afla numărul natural N, reprezentând numărul de copaci.

Pe cea de-a doua linie vor exista N numere naturale nenule reprezentând înălțimile celor N copaci.

Pe cea de-a treia linie se vor afla două numere naturale T1 și T2 reprezentând tariful pe metru al muncitorului 1 respectiv al muncitorului 2.

Pe ultima linie se vor afla două numere naturale C1 și C2 reprezentând costul suplimentar cerut de muncitorul 1 respectiv muncitorul 2.

Date de ieșire

În fișierul democratie.out se va scrie, pe prima și singura linie din fișier, costul minim pe care Arpsod trebuie să-l plătească.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ T1, T2 ≤ 100
1 ≤ C1, C2 ≤ 10.000
1 ≤ H_i ≤ 100
Se garantează că pentru 20% din teste 1 ≤ N ≤ 10
Costul suplimentar este același indiferent de înălțimea copacului ce va fi tăiat.
Este posibil ca un muncitor să taie singur toți copacii.
Un muncitor va tăia complet un copac.
Cam scumpă democrația asta!

Exemplu:

democratie.in

democratie.out

Explicație

Ordinea muncitorilor:

M2 -> M1 -> M2 -> M2

Costul: (2*4) + (7*1) + (2*3) + (2*2 + 9)

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import sys

Nmax = 100002 inf = 2000000000

N, T1, T2, C1, C2 = 0, 0, 0, 0, 0 v = [0] * Nmax Sol = inf config = [0] * Nmax

def bkt(poz):

   global N, T1, T2, C1, C2, Sol, v, config

   if poz > N:
       st, dr = 1, N
       Total = 0

       for i in range(1, N + 1):
           if config[i] == 1:
               Total += v[st] * T1
               st += 1

               if config[i - 1] == config[i]:
                   Total += C1
           else:
               Total += v[dr] * T2
               dr -= 1

               if config[i - 1] == config[i]:
                   Total += C2

       Sol = min(Sol, Total)
       return

   for i in range(1, 3):
       config[poz] = i
       bkt(poz + 1)

def main():

   global N, T1, T2, C1, C2, Sol, v, config

   lines = sys.stdin.readlines()
   N = int(lines[0])

   v = list(map(int, lines[1].split()))

   T1, T2, C1, C2 = map(int, lines[2].split())

   bkt(1)

   print(Sol)

if __name__ == "__main__":

   main()

</syntaxhighlight>