Advertisement
anon20016

K

Nov 22nd, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9.  
  10. #define ull unsigned long long
  11. #define ll long long
  12.  
  13. using namespace std;
  14.  
  15. const int N = 1001;
  16. const ll INF = 1000ll * 1000 * 1000;
  17.  
  18. //ll a[N];
  19. pair<int, int> d[N];
  20. int p[N];
  21.  
  22. int dx[3] = { 2, 3, 6 };
  23.  
  24. int main() {
  25.     //freopen("input.txt", "r", stdin);
  26.     //freopen("output.txt", "w", stdout);
  27.     int n;
  28.     cin >> n;
  29.     vector<int> a(n);
  30.     for (int i = 0; i < n; i++) {
  31.         cin >> a[n - i - 1];
  32.     }
  33.     vector<int> d(n + 1, INF);
  34.     d[0] = -INF;
  35.  
  36.     for (int i = 0; i < n; i++) {
  37.         int j = int(upper_bound(d.begin(), d.end(), a[i]) - d.begin());
  38.         if (d[j - 1] <= a[i] && a[i] <= d[j])
  39.             d[j] = a[i];
  40.     }
  41.     int ans = 0;
  42.     for (int i = 0; i <= n; i++) {
  43.         if (d[i] != INF) {
  44.             ans = i;
  45.         }
  46.     }
  47.     cout << ans;
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement