Cod sursa(job #2989526)

Utilizator raresgherasaRares Gherasa raresgherasa Data 6 martie 2023 18:46:06
Problema Secv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 5e3 + 5;

int answer = INT_MAX, sz, n;
int a[N_MAX], f[N_MAX], dp[N_MAX];

void precalc (){
   set<int>s;
   map<int, int>mp;
   for (int i = 1; i <= n; i++){
      s.insert(a[i]);
   }
   int cnt = 0;
   for (int x : s){
      ++cnt;
      mp[x] = cnt;
   }
   for (int i = 1; i <= n; i++){
      a[i] = mp[a[i]];
   }
   sz = cnt;
}

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n;
   for (int i = 1; i <= n; i++){
      fin >> a[i];
   }
   precalc();
   for (int i = 1; i <= n; i++){
      int cnt = 0;
      for (int j = i; j <= n; j++){
         dp[a[j]] = 1 + dp[a[j] - 1];
         if (++f[a[j]] == 1){
            ++cnt;
         }
         if (cnt == sz && dp[sz] == sz){
            answer = min(answer, j - i + 1);
         }
      }
      memset(dp, 0, sizeof(dp));
      memset(f, 0, sizeof(f));
   }
   fout << (answer == INT_MAX ? -1 : answer);
}