Cod sursa(job #2221820)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 15 iulie 2018 22:30:54
Problema Secv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("secv.in");
ofstream fout ("secv.out");

const int inf=0x3f3f3f3f;
const int nmax=5002;

struct nv{
    int x,y;
}a[nmax];

int n,v[nmax],k,d[nmax],l[nmax],mini=inf;

bool sortf(nv q, nv qq){
    return (q.x<qq.x )||(q.x==qq.x && q.y<qq.y);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;++i){fin>>a[i].x;a[i].y=i;}
    sort(a+1,a+n+1,sortf);
    a[0].x=-1;
    for(int i=1;i<=n;++i){
        if(a[i].x!=a[i-1].x)k++;
        v[a[i].y]=k;
    }
    memset(l,0,sizeof l);
    for(int i=1;i<=n;++i){
        if(v[i]==1)d[i]=1;
        else if(l[v[i]-1] && d[l[v[i]-1]])
            d[i]=d[l[v[i]-1]]+i-l[v[i]-1];
        l[v[i]]=i;
    }
    for(int i=1;i<=n;++i)
        if(v[i]==k && d[i])mini=min(mini,d[i]);
    fout<<((mini==inf)?-1:mini)<<'\n';
    return 0;
}