SHARE
TWEET

Untitled

a guest Nov 16th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <ctime>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <map>
  8. #include <set>
  9. #include <iomanip>
  10. #include <string>
  11.  
  12. #define f first
  13. #define s second
  14. #define pb push_back
  15. #define ll long long
  16. using namespace std;
  17. const int N = 1e6+5;
  18. int a[N], dp[N], p[N];
  19.  
  20. int main() {
  21.     ios_base::sync_with_stdio(0);
  22.     cin.tie(0); cout.tie(0);
  23.     int n;
  24.     cin >> n;
  25.     for (int i = 0; i < n; ++i)
  26.         cin >> a[i];
  27.    
  28.     for (int i = 0; i < n; ++i) {
  29.         dp[i] = 1;
  30.         for (int j = 0; j < i-1; ++j)
  31.             if (a[i] > a[j])
  32.                 dp[i] = max(dp[i], dp[j]+1);
  33.     }
  34.     cout << dp[n-1] << '\n';
  35.     int len = dp[n-1];
  36.    
  37.     for (int i = 0; i < n; ++i) {
  38.         for (int j = 0; j < i-1; ++j) {
  39.             if (a[i] > a[j]) {
  40.                 if (dp[i] < dp[j]+1) {
  41.                     dp[i] = dp[j] + 1;
  42.                     p[i] = j;
  43.                 }
  44.             }
  45.         }
  46.     }
  47.    
  48.     for (int i = 0; i < n; ++i)
  49.         cout << p[i] << " ";
  50.    
  51.     cout << '\n';
  52.    
  53.     for (int i = 0; i < len; ++i)
  54.         cout << a[p[i]] << " ";
  55.    
  56.     return 0;
  57. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top