Cod sursa(job #2072732)

Utilizator grecubogdanGrecu Bogdan grecubogdan Data 22 noiembrie 2017 10:08:18
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv.in");
ofstream fout("secv.out");
int n,a[5005],b[5005],ct;
map <int,int> m;
map <int,int> t;
int lg[5005],nr[5005];
int main()
{
    int i;
fin>>n;
for(i=1;i<=n;i++)
    {fin>>a[i];
    m[a[i]]++;
    if(m[a[i]]==1)
    b[++ct]=a[i];
    }
sort(b+1,b+ct+1);
for(i=1;i<=ct;i++)
    {m[b[i]]=i;
    nr[i]=-1;
    }
for(i=1;i<=n;i++)
{
    if(a[i]==b[1])
    {
        nr[1]=i;
        lg[i]=1;
    }
    else
        if(nr[m[a[i]]-1]!=-1)
            {
                nr[m[a[i]]]=i;
                lg[i]=(i-nr[m[a[i]]-1])+lg[nr[m[a[i]]-1]];
            }
}
if(nr[ct]==-1)
    fout<<-1;
else
    if(n)
{int mini=9999;
for(i=1;i<=n;i++)
    if(a[i]==b[ct]&&nr[ct]!=-1)
        if(lg[i]<mini&&lg[i]>=ct)
            mini=lg[i];
fout<<mini;
}
    else
        fout<<0;
    return 0;
}