Advertisement
double_trouble

А

Apr 7th, 2016
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <string>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <set>
  9. #include <queue>
  10.  
  11. using namespace std;
  12.  
  13. struct sz
  14. {
  15.     int w, h, k;
  16.     sz():w(0), h(0), k(0){}
  17.     sz(int _w, int _h, int _k) :w(_w), h(_h), k(_k) {}
  18. };
  19.  
  20. bool operator< (sz x, sz y)
  21. {
  22.     return x.w < y.w && x.h < y.h;
  23. }
  24.  
  25. bool operator==(sz x, sz y)
  26. {
  27.     return x.w == y.w && x.h == y.h;
  28. }
  29.  
  30. vector<sz> a;
  31. vector<int> d;
  32. vector<pair<int, int> > f;
  33.  
  34. int main()
  35. {
  36.     ios_base::sync_with_stdio(0);
  37.     cin.tie(0);
  38.     cout.tie(0);
  39.  
  40.     int n, w, h;
  41.     cin >> n >> w >> h;
  42.  
  43.     int ww, hh;
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         cin >> ww >> hh;
  47.         if (ww <= w || hh <= h)
  48.             continue;
  49.         a.push_back(sz(ww, hh, i + 1));
  50.     }
  51.  
  52.     if (a.size() < 2)
  53.     {
  54.         cout << a.size() << endl;
  55.         for (int i = a.size() - 1; i >= 0; i--)
  56.             cout << a[i].k << " ";
  57.         return 0;
  58.     }
  59.  
  60.     sort(a.begin(), a.end());
  61.  
  62.     f.resize(a.size(), make_pair(1, -1));
  63.  
  64.     for (int i = 1; i < a.size(); i++)
  65.         for (int j = 0; j < i; j++)
  66.         {
  67.             if (a[j] < a[i] && f[i].first < f[j].first + 1)
  68.                 f[i] = make_pair(f[j].first + 1, j);
  69.         }
  70.  
  71.     int ans = 0;
  72.     int r = 0;
  73.     sz t;
  74.     for (int i = 0; i < a.size(); i++)
  75.     {
  76.         if (f[i].first > ans)
  77.         {
  78.             ans = f[i].first;
  79.             t = a[i];
  80.             r = i;
  81.         }
  82.     }
  83.    
  84.     while (f[r].second != -1)
  85.     {
  86.         d.push_back(a[r].k);
  87.         r = f[r].second;
  88.     }
  89.  
  90.     d.push_back(a[r].k);
  91.  
  92.     cout << d.size() << endl;
  93.     for (int i = d.size() - 1; i >= 0; i--)
  94.         cout << d[i] << " ";
  95.  
  96.  
  97.     return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement