raghuvanshraj

354.cpp

Jul 26th, 2021
657
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  10.03.2020 12:53:21 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. bool operator<(vector<int> &a, vector<int> &b) {
  10.     return ((a[0] < b[0]) and (a[1] < b[1]));
  11. }
  12.  
  13. int maxEnvelopes(vector<vector<int>> envelopes) {
  14.     sort(envelopes.begin(), envelopes.end());
  15.  
  16.     int n = envelopes.size();
  17.     if (n == 0) {
  18.         return 0;
  19.     }
  20.  
  21.     vector<int> dp(n, 1);
  22.     for (int i = 0; i < n; ++i) {
  23.         for (int j = i - 1; j >= 0; --j) {
  24.             if (envelopes[j] < envelopes[i]) {
  25.                 dp[i] = max(dp[i], dp[j] + 1);
  26.             }
  27.         }
  28.     }
  29.  
  30.     return *max_element(dp.begin(), dp.end());
  31. }
  32.  
  33. int main(int argc, char const *argv[]) {
  34.     int n;
  35.     cin >> n;
  36.     vector<vector<int>> envelopes(n, vector<int>(2));
  37.     for (int i = 0; i < n; ++i) {
  38.         cin >> envelopes[i][0] >> envelopes[i][1];
  39.     }
  40.  
  41.     cout << maxEnvelopes(envelopes);
  42.  
  43.     return 0;
  44. }
RAW Paste Data