# PBinfo #4427 – secvmin – Rezolvare C++

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

## Enunț

Fie un șir de n numere naturale v[1], v[2], …, v[n], unde v[i] reprezintă al i-lea număr din șir. O subsecvență [x, y] a șirului v (cu 1 ≤ x ≤ y ≤ n) conține toate elementele v[x], v[x+1], ...,  v[y - 1], v[y].

Cerința
Fiind date două numere naturale n și k și un șir v de n numere naturale, scrieți un program care să răspundă la următoarea întrebare: câte subsecvențe conțin simultan cele mai mici k valori distincte din șir?

Date de intrare
Fișierul de intrare secvmin.in conține pe prima linie numerele n și k, iar pe cea de a doua linie se vor afla numerele naturale v[1], v[2], …, v[n], cu semnificația din enunț. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire secvmin.out va conține o singură linie pe care va fi scris răspunsul la cerința problemei.

Restricții și precizări

1 ≤ n ≤ 1.000.000
1 ≤ k ≤ 5
1 ≤ v[i] ≤ 1.000.000.000, pentru 1 ≤ i ≤ n
Se garantează că șirul va conține cel puțin k valori distincte.

Exemplul 1:
secvmin.in

7 1
1 3 2 2 1 3 2
secvmin.out

19
Explicație
k=1. Cea mai mică valoare din șir este egală cu 1. Subsecvențele care conțin valoarea 1 sunt:
[1 1], [1 2], [1 3], [1 4], [1 5], [1 6], [1 7],
[2 5], [2 6], [2 7],
[3 5], [3 6], [3 7],
[4 5], [4 6], [4 7],
[5 5], [5 6], [5 7].

Exemplul 2:
secvmin.in

7 2
1 5 2 2 1 5 2
secvmin.out

15
Explicație
k=2. Cea mai mică valoare din șir este egală cu 1, iar a doua cea mai mică valoare din șir este egală cu 2.
Subsecvențele care conțin valorile 1 și 2 sunt:
[1 3], [1 4], [1 5], [1 6], [1 7],
[2 5], [2 6], [2 7],
[3 5], [3 6], [3 7],
[4 5], [4 6], [4 7],
[5 7].

## Cod sursă C++

```cpp
//A. Panaete 100
#include <bits/stdc++.h>
using namespace std;
ifstream f("secvmin.in");
ofstream g("secvmin.out");
const int N = 1000010;
int n,k,x[N],y[10],last[10];
int64_t sol;
int main()
{
    f>>n>>k;
    for(int i=1;i<=k;i++)y[i]=1000000010;
    for(int i=1; i<=n; i++)
    {
        int val;
        f>>val;
        if(val<y[k])
        {
            int p=1;
            while(val>y[p])p++;
            if(val<y[p])
            {
                int  q=k;
                while(q>p)
                {
                    y[q]=y[q-1];
                    q--;
                }
                y[p]=val;
            }
        }
        x[i]=val;
    }
    for(int i=1; i<=n; i++)
    {
        int cnt=n+1;
        for(int j=1; j<=k; j++)
        {
            if(x[i]==y[j])last[j]=i;
            cnt=min(cnt,last[j]);
        }
        sol+=cnt;
    }
    g<<sol;
    return 0;
}
```

## Resurse

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