Zadanie "Smakołyki" - optymalizacja kodu

Witam, mam takie zadanie (z MAIN):

Natalia ustawiła w rzędzie n smakołyków. Każdy smakołyk ma przypisany pewien rodzaj. Natalia może teraz
wybrać pewną liczbę (od 1 do n) sąsiednich smakołyków, a następnie je wszystkie zjeść. Jedynym warunkiem
jest to, aby żadne dwa smakołyki nie były tego samego rodzaju. Pomóż Natalii i znajdź liczbę sposobów, na
które może wybrać sąsiednie smakołyki.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n, m (1 ≤ n, m ≤ 1 000 000), oznaczające odpowiednio
liczbę smakołyków oraz liczbę dostępnych ich rodzajów. Drugi wiersz zawiera n liczb całkowitych
c0, c1, . . . , cn−1 (1 ≤ ci ≤ m), gdzie ci oznacza rodzaj i-tego smakołyka.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą liczbie sposobów, na które
Natalia może wybrać sąsiednie smakołyki.

Napisałem taki kod:

#include <iostream>
using namespace std;

void zerowanie(bool tablica[], int n)
{
    for(int i = 0; i < n; i++)
        tablica[i] = false;
}

int main()
{
    int n, m;
    int sposoby = 0;
    cin >> n >> m;
    int smakolyki[n];
    bool sprawdzenie[m + 1];
    for(int i = 0; i < n; i++)
        cin >> smakolyki[i];
    int j;
    for(int i = 0; i < n; i++)
    {
        zerowanie(sprawdzenie, m + 1);
        j = i;
        while(j < n && !sprawdzenie[smakolyki[j]])
        {
            sposoby++;
            sprawdzenie[smakolyki[j]] = true;
            j++;
        }
    }
    cout << sposoby << endl;

    return 0;
}

Nie chce mi zaliczyć zadania, bo moje rozwiązanie przekracza czas. Jak je zoptymalizować? Zaznaczam, że dopiero uczę się programować i dlatego proszę o pomoc dla osoby na moim poziomie, żebym zrozumiał.

A może zrobić mapę (http://pl.cppreference.com/w/cpp/container/map)? Skoro jakiś smakołyk występuje na miejscu 2 a potem piątym, to znaczy że od miejsca drugiego może wziąć na 5 - 2 = 3 sposoby: 2 albo 2 i 3, oraz 2, 3 i 4. Jak występuje tylko raz albo badamy ostatnie jego wystąpienie, to wtedy bierzemy n.

Udało mi się rozwiązać. Nie znam zasad tego forum, ale jeśli to dozwolone to wklejam rozwiązanie (nie znalazłem na internecie), gdyby ktoś w przyszłości miał z tym problem.

#include <iostream>
using namespace std;

void zerowanie(bool tablica[], int n)
{
    for(int i = 0; i < n; i++)
        tablica[i] = false;
}

int main()
{
    int n, m;
    long long int sposoby = 0;
    cin >> n >> m;
    int smakolyki[n];
    bool sprawdzenie[m + 1];
    for(int i = 0; i < n; i++)
        cin >> smakolyki[i];
    int j, k = 0, l = 1;
    zerowanie(sprawdzenie, m + 1);
    for(int i = 0; i < n; i++)
    {
        if(!sprawdzenie[smakolyki[i]])
        {
            sposoby += l;
            sprawdzenie[smakolyki[i]] = true;
            l++;
        }
        else
        {
            for(j = k; j < n; j++)
            {
                l--;
                if(smakolyki[j] != smakolyki[i])
                {
                    sprawdzenie[smakolyki[j]] = false;
                    k++;
                }
                else
                {
                    if(l != 0)
                        sposoby += l;
                    else
                        sposoby++;
                    k++;
                    l++;
                    break;
                }
            }
        }
    }
    cout << sposoby << endl;

    return 0;
}