# PBinfo #3659 – SumMaxSecv – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Pentru că e criză, cu ocazia campaniei electorale, în loc de găleți pline cu făină, zahăr și bilete la teatru primiți un șir a1, a2, …, an care reprezintă o permutare a mulțimii {1,2,...,n}. Pentru fiecare secvență nevidă a permutării costul ei este valoarea maximă din acea secvență. De exemplu, costul secvenței 4,2,6,1,3,5 este 6, iar costul secvenței 4,2 este 4.

Cerința
Să se calculeze suma totală a costurilor tuturor secvențelor.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi șirul de n numere naturale, separate prin spații.

Date de ieșire
Programul va afișa pe ecran numărul S, reprezentând suma costurilor tuturor secvențelor.

Restricții și precizări

2 ≤ n ≤ 100.000
șirul de numere este o permutare a mulțimii {1,2,...,n}

Exemplu:
Intrare

4
2 3 4 1
Ieșire

33
Explicație
Secvențele nevide ale permutării 2,3,4,1 sunt:
2 – cost 2
2 3 – cost 3
2 3 4 – cost 4
2 3 4 1 – cost 4
3 – cost 3
3 4 – cost 4
3 4 1 – cost 4
4 – cost 4
4 1 – cost 4
1 – cost 1
Costul total este 2+3+4+4+3+4+4+4+4+1=33.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define nmax 100003
using namespace std;
int a[nmax], st[nmax], dr[nmax], n;
void Citire()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = a[n + 1] = n + 1;
}
void StangaDreapta()
{
    int i, x;
    stack<int> q;
    q.push(0);
    for (i = 1; i <= n; i++)
    {
        x = a[i];
        while (x > a[q.top()])
            q.pop();
        st[i] = i - q.top();
        q.push(i);
    }
    /// golire stiva
    while (!q.empty()) q.pop();
    q.push(n + 1);
    for (i = n; i >= 1; i--)
    {
        x = a[i];
        while (x > a[q.top()])
            q.pop();
        dr[i] = q.top() - i;
        q.push(i);
    }
}
void CostTotal()
{
    long long cost = 0;
    for (int i = 1; i <= n; i++)
        cost += 1LL * st[i] * dr[i] * a[i];
    cout << cost << "\n";
}
int main()
{
    Citire();
    StangaDreapta();
    CostTotal();
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3659)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3659/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3659/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)