Pagini recente » Cod sursa (job #749538) | Cod sursa (job #2944416) | Cod sursa (job #1251354) | Cod sursa (job #1157622) | Cod sursa (job #2241293)
#include <bits/stdc++.h>
using namespace std;
ifstream in("euro2.in");
ofstream out("euro2.out");
const int NMAX = 10005;
int v[NMAX],nrm[NMAX],dp1[NMAX],dp2[NMAX],fn[NMAX],n;
int query(int x)
{
int Max = 0;
while (x>0)
{
if (fn[x]>Max)
Max = fn[x];
x-=x&-x;
}
return Max;
}
void update(int val, int x)
{
while (x<=n)
{
if (val>fn[x])
fn[x] = val;
x+=x&-x;
}
}
int main()
{
in >> n;
for (int i = 1; i<=n; i++)
{
int x = 0;
string s;
in >> s;
for (auto it: s)
if (it!='.')
x = x*10+it-'0';
v[i] = nrm[i] = x;
}
sort(nrm+1,nrm+n+1);
int h = 1;
for (int i = 2; i<=n; i++)
if (nrm[i]!=nrm[i-1])
nrm[++h] = nrm[i];
for (int i = 1; i<=n; i++)
v[i] = lower_bound(nrm+1,nrm+n+1,v[i])-nrm;
for (int i = 1; i<=n; i++)
{
dp1[i] = query(v[i]-1)+1;
update(dp1[i],v[i]);
}
reverse(v+1,v+n+1);
memset(fn,0,sizeof(fn));
for (int i = 1; i<=n; i++)
{
dp2[i] = query(v[i]-1)+1;
update(dp2[i],v[i]);
}
int Max = 0;
for (int i = 1; i<=n; i++)
if (dp1[i]>=2 && dp2[i]>=2)
Max = max(Max,dp1[i]+dp2[n-i+1]-1);
out << Max;
}