Cod sursa(job #2650359)

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

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

vector<pair<int, int>> v;
bool cmp(pair<int, int> a, pair<int, int> b){
  return a.second<b.second;
}

int main()
{
  int n;
  fin>>n;
  v.resize(n+1);
  for(int i=1;i<=n;++i){
    fin>>v[i].first;
    v[i].second=i;
  }
  sort(v.begin()+1, v.end());
  for(int i=1;i<=n;++i){
    if(v[i].first!=v[i-1].first) v[i].first=v[i-1].first+1;
  }
  int maxi=v[n].first;
  sort(v.begin()+1, v.end(), cmp);
  vector<int> dp(n+1);
  int last[n+1]={0};
  int sol=(1<<30);
  for(int i=1;i<=n;++i){
    if(v[i].first==1) dp[i]=1;
    else{
      int pos=last[v[i].first-1], dist=i-pos;
      if(pos) dp[i]=dp[pos]+dist;
      else dp[i]=(1<<25);
      if(v[i].first==maxi) sol=min(sol, dp[i]);
    }
    last[v[i].first]=i;
  }
  if(sol>=(1<<25)) fout<<-1<<"\n";
  else fout<<sol<<"\n";
  return 0;
}