1755 - Democratie

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ă, Hi. 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 ≤ Hi ≤ 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

4
1 2 3 4
7 2
3 9

democratie.out

34

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

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()