Cod sursa(job #2650362)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 18 septembrie 2020 15:30:03
Problema Secv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

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

map<int, int> nrm;

vector<int> v;


int main()
{
  int n;
  fin>>n;
  v.resize(n+1);
  int maxi=0;
  for(int i=1;i<=n;++i){
    fin>>v[i];
    nrm[v[i]]++;
    if(nrm[v[i]]==1) maxi++;
  }
  int cnt=0;
  for(auto it:nrm){
    nrm[it.first]=++cnt;
  }
  for(int i=1;i<=n;++i){
    v[i]=nrm[v[i]];
  }
  vector<int> dp(n+1);
  int last[n+1]={0};
  int sol=(1<<30);
  for(int i=1;i<=n;++i){
    if(v[i]==1) dp[i]=1;
    else{
      int pos=last[v[i]-1], dist=i-pos;
      if(pos) dp[i]=dp[pos]+dist;
      else dp[i]=(1<<25);
    }
    if(v[i]==maxi) sol=min(sol, dp[i]);
    last[v[i]]=i;
  }
  if(sol>=(1<<25)) fout<<-1<<"\n";
  else fout<<sol<<"\n";
  return 0;
}