Pagini recente » Cod sursa (job #854964) | Istoria paginii runda/trainingtime | Monitorul de evaluare | Cod sursa (job #1990396) | Cod sursa (job #2022487)
#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;
}