Advertisement
Saleh127

UVA 10534 / LIS-LDS

Sep 29th, 2021
1,176
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5.  
  6. ll lis[10005];
  7. ll lds[10005];
  8. ll a[10005];
  9.  
  10. int main()
  11. {
  12.    ios_base::sync_with_stdio(0);
  13.    cin.tie(0);cout.tie(0);
  14.  
  15.    ll n,m,i,j,k,l;
  16.  
  17.    while(cin>>n)
  18.    {
  19.         vector<ll>x(n);
  20.  
  21.         for(i=0;i<n;i++)
  22.         {
  23.              cin>>x[i];
  24.         }
  25.  
  26.         for(i=0;i<n+4;i++) a[i]=1e9;
  27.  
  28.         for(i=0;i<n;i++)
  29.         {
  30.              k=lower_bound(a,a+n,x[i])-a;
  31.              lis[i]=k+1;
  32.              a[k]=x[i];
  33.         }
  34.  
  35.         reverse(x.begin(),x.end());
  36.  
  37.         for(i=0;i<n+4;i++) a[i]=1e9;
  38.  
  39.         for(i=0;i<n;i++)
  40.         {
  41.              k=lower_bound(a,a+n,x[i])-a;
  42.              lds[i]=k+1;
  43.              a[k]=x[i];
  44.         }
  45.  
  46.         l=0;
  47.  
  48.         for(i=0;i<n;i++)
  49.         {
  50.              k=min(lis[i],lds[n-i-1]);
  51.              k*=2;
  52.              l=max(l,k-1);
  53.         }
  54.  
  55.         cout<<l<<endl;
  56.  
  57.         memset(lis,0,sizeof lis);
  58.         memset(lds,0,sizeof lds);
  59.    }
  60.  
  61.  
  62.    return 0;
  63. }
  64.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement