Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N articole de îmbrăcăminte și încălțăminte cu preturile s1, s2, …, sN lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:

Maria este mare amatoare de cumpărături. Ea și-a cumpărat în decursul mai multor zile de la magazinul său preferat N articole de îmbrăcăminte și încălțăminte cu preturile s1, s2, …, sN lei. Iulia, prietena Mariei, observând cumpărăturile, i-a spus:
– Puteai economisi mulți bani. Nu ai văzut promoțiile magazinului? Dacă ai fi cumpărat două produse deodată, cel mai ieftin din cele două l-ai fi cumpărat la jumătate de preț. Iar dacă ai fi cumpărat trei produse deodată, ai fi primit pe cel mai ieftin din cele trei gratuit!
Maria și Iulia s-au decis să afle care ar fi fost suma minimă cheltuită pentru a achiziționa în aceeași ordine cele N produse, dar grupând câte un produs, câte două sau câte trei.

Cerința

Pentru că cele două fete nu se descurcă așa de bine la informatică, ele te roagă să le ajuți să determine care este această sumă minimă.

Date de intrare

Programul citește de la tastatură un număr natural N, iar apoi N numere naturale s1, s2, …, sN separate prin câte un spațiu reprezentând sumele cheltuite pentru fiecare din cele N produse.

Date de ieșire

Programul va afișa pe ecran un singur număr real, care reprezintă suma minimă ce putea fi cheltuită grupând produsele câte unul, câte două sau câte trei. Numărul real se va afișa cu o zecimală.

Restricții și precizări

• 4 ≤ N ≤ 1000
• Sumele s1, s2, …, sN sunt numere naturale cuprinse între 1 și 1000

Exemplul 1:

Intrare

4
20 100 50 200

Ieșire

320.0

Explicație

Maria trebuia să cumpere primul produs, cheltuind 20 lei, apoi să cumpere ultimele trei produse împreună cheltuind numai 300 de lei, deoarece produsul de 50 lei îl primea gratuit.

Exemplul 2:

Intrare

5
100 27 15 25 400

Ieșire

538.5

Explicație

Maria trebuia să cumpere primele două produse împreună, cheltuind 113.5 lei, apoi să cumpere ultimele trei produse împreună, cheltuind 425 lei. Suma totală cheltuită ar fi fost 113.5 + 425 = 538.5 lei.

#include <bits/stdc++.h>

using namespace std;

int a[1001], n;
double sum[1001];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + a[i];
        if(i >= 2) sum[i] = min(sum[i], sum[i - 2] + 1.00 * min(a[i], a[i - 1])/2 + max(a[i], a[i - 1]));
        if(i >= 3) sum[i] = min(sum[i], sum[i - 3] + a[i] + a[i - 1] + a[i - 2] - min(a[i], min(a[i - 1], a[i - 2])));
    }
    cout << fixed << setprecision(1) << sum[n];
    return 0;
}