# PBinfo #3499 – Secv011 – Rezolvare C++

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

## Enunț

Se dă un șir \(A\) format din \(n\) elemente din mulțimea \(\{0, 1\}\). Numim secvență a șirului \(A\) orice succesiune de elemente situate pe poziții consecutive în șir.

Cerința
Să se determine numărul de secvențe ale șirului \(A\) ce conțin de două ori mai mulți de \(1\) decât de \(0\).

Date de intrare
Pe prima linie a fișierului secv011.in se află numărul \(n\). Pe următoarea linie se află cele \(n\) elemente ale șirului \(A\), separate prin câte un spațiu.

Date de ieșire
Fișierul secv011.out va conține pe prima linie numărul cerut.

Restricții și precizări

Pentru teste în valoare de 20 de puncte, \(1 \le n \le 1.000\).
Pentru teste în valoare de 50 de puncte, \(1 \le n \le 5.000\).
Pentru teste în valoare de 100 de puncte, \(1 \le n \le 1.000.000\).

Exemplu:
secv011.in

6
1 0 1 1 1 0
secv011.out

4
Explicație
Secvențele cu proprietatea dată sunt \((1, 0, 1)\), \((0, 1, 1)\), \((1, 1, 0)\) și \((1, 0, 1, 1, 1, 0)\).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv011.in");
ofstream fout("secv011.out");
int main() {
    int n; fin >> n;
    vector<int> frq(3 * n + 1);
    frq[n] = 1;
    int ps = 0;
    int64_t sol = 0;
    for (int i = 1; i <= n; i++) {
        bool x; fin >> x; ps += x;
        sol += frq[2 * i - 3 * ps + n]++;
    }
    fout << sol << '\n';
    fout.close();
    return 0;
}
```

## Resurse

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