Cod sursa(job #2549494)
Utilizator | Iceman bem.andrei | Data | 17 februarie 2020 18:59:16 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 20 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.49 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream r("scmax.in");
ofstream w("scmax.out");
int v[100001], f[100001];
int cautbin(int n)
{
int st=0, dr=99999, mij, p=1;
while (st<=dr)
{
mij=(st+dr)/2;
if(v[mij]>=n)
{
p=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return p;
}
int main()
{
int n, cnt=0, maxim=0, var=1999999999;
r>>n;
for(int i=0; i<n; i++)
{
int k;
r>>k;
if(k>=v[cnt] && k<=var)
{
if(k!=v[cnt])
{
cnt++;
v[cnt]=k;
}
}
else
{
if(k<v[cnt])
{
if(cnt>maxim)
{
maxim=cnt;
for(int j=0; j<=cnt; j++)
{
f[j]=v[j];
}
var=v[cnt];
}
cnt=cautbin(k);
v[cnt]=k;
}
else
{
maxim=max(maxim,cnt);
maxim++;
f[maxim]=k;
}
}
}
if(cnt>maxim)
{
maxim=cnt;
for(int j=0; j<=cnt; j++)
{
f[j]=v[j];
}
}
w<<maxim<<"\n";
for(int i=1; i<=maxim; i++)
{
w<<f[i]<<" ";
}
return 0;
}