Cod sursa(job #2022487)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 16 septembrie 2017 17:01:30
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <vector>
#define VAL 5005
#define INF 1000005

using namespace std;

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

int N, M, i, j, mx;
int v[VAL], ind[VAL];
int dp[VAL], mn, poz;
vector <int> SOL;

int Binary_Search(int nr)
{
    int be=0, en=mx;
    int mid, ans=0;
    while (be<=en)
    {
        mid=(be+en) / 2;
        if (ind[mid]<=nr)
        {
            ans=mid;
            be=mid+1;
        }
        else
          en=mid-1;
    }
    return ans;
}

int main()
{
    fin >> N;
    for (i=0; i<=N; i++)
      ind[i]=-INF;
    for (i=1; i<=N; i++)
    {
        fin >> v[i];
        dp[i]=Binary_Search(v[i])+1;
        mx=max(mx, dp[i]);
        if (ind[dp[i]]==-INF)
          ind[dp[i]]=v[i];
        else
          ind[dp[i]]=min(ind[dp[i]], v[i]);
    }
    mx=0;
    mn=INF;
    for (i=N; i>=1; i--)
    {
        if (v[i]>mx)
        {
            mx=v[i];
            if (mn>dp[i])
            {
                mn=dp[i];
                poz=i;
            }
        }
    }
    fout << mn << '\n';
    mn--;
    SOL.push_back(poz);
    for (i=poz-1; i>0; i--)
    {
        if (mn==0)
          break;
        if (dp[i]==mn)
        {
            SOL.push_back(i);
            mn--;
        }
    }
    for (i=SOL.size()-1; i>=0; i--)
      fout << SOL[i] << " ";
    fin.close();
    fout.close();
    return 0;
}