ccbeginner

UVa Q10534

Feb 7th, 2020
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10534
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int arr[10000];
  6. int big[10000], small[10000];//ascend, descend
  7.  
  8. int main(){
  9.     int n;
  10.     while(cin >> n){
  11.         for(int i = 0; i < n; ++i)cin >> arr[i];
  12.         vector<int> v1,v2;
  13.         v1.emplace_back(arr[0]);
  14.         big[0] = 1;
  15.         for(int i = 1; i < n; ++i){
  16.             if(arr[i] > v1.back()){
  17.                 big[i] = v1.size()+1;
  18.                 v1.emplace_back(arr[i]);
  19.             }else{
  20.                 auto it = lower_bound(v1.begin(), v1.end(), arr[i]);
  21.                 big[i] = it-v1.begin()+1;
  22.                 (*it) = arr[i];
  23.             }
  24.         }
  25.         v2.emplace_back(arr[n-1]);
  26.         small[n-1] = 1;
  27.         for(int i = n-2; i >= 0; --i){
  28.             if(arr[i] > v2.back()){
  29.                 small[i] = v2.size()+1;
  30.                 v2.emplace_back(arr[i]);
  31.             }else{
  32.                 auto it = lower_bound(v2.begin(), v2.end(), arr[i]);
  33.                 small[i] = it-v2.begin()+1;
  34.                 (*it) = arr[i];
  35.             }
  36.         }
  37.         /*for(int i = 0; i < n; ++i)cout << big[i] << ' ';
  38.         cout << endl;
  39.         for(int i = 0; i < n; ++i)cout << small[i] << ' ';
  40.         cout << endl;*/
  41.         int ans = 0;
  42.         for(int i = 0; i < n; ++i)ans = max(ans, min(big[i], small[i]));
  43.         cout << ans*2-1 << '\n';
  44.     }
  45.     return 0;
  46. }
RAW Paste Data