Editing 1755 - Democratie

Arpsod are în curtea sa <code>N</code> copaci foarte bătrâni, așezați în linie și numerotați de la <code>1</code> la <code>N</code>. Fiecare copac are o înălțime cunoscută, <code>H<sub>i</sub></code>. 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 <code>1, 2, 3, ... ,N</code> iar cel de-al doilea în ordinea <code>N, N-1, N-2, ... 1</code>.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul <code>1</code> are un tarif de <code>T1</code> pe metru iar muncitorul <code>2</code> un tarif de <code>T2</code> 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 <code>C</code> pentru a rămâne să taie în continuare.

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

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

= Date de intrare =
Pe prima linie a fișierului <code>democratie.in</code> se va afla numărul natural <code>N</code>, reprezentând numărul de copaci. 

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

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

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

= Date de ieșire =
În fișierul <code>democratie.out</code> 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 =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ T1, T2 ≤ 100</code>
* <code>1 ≤ C1, C2 ≤ 10.000</code>
* <code>1 ≤ H<sub>i</sub> ≤ 100</code>
* Se garantează că pentru <code>20%</code> din teste <code>1 ≤ N ≤ 10</code>
* 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: =
<code>democratie.in</code>
 4
 1 2 3 4
 7 2
 3 9
<code>democratie.out</code>
 34

=== Explicație ===
Ordinea muncitorilor:

<code>M2 -> M1 -> M2 -> M2</code>

Costul: <code>(2*4) + (7*1) + (2*3) + (2*2 + 9)</code>

== Î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>