Dang_Quan_10_Tin

HCN TS10 PTNK 2007-2008

Jan 15th, 2022
862
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "HCN"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11.  
  12. constexpr int N = 1e2 + 5;
  13. int n, f[N];
  14. struct Rectangle
  15. {
  16.     int x, y, z, t;
  17.     bool operator<(const Rectangle &a) const
  18.     {
  19.         return x < a.x || (x == a.x && (y < a.y || (y == a.y && (z < a.z || (z == a.z && t < a.t)))));
  20.     }
  21. } a[N];
  22.  
  23. void Read()
  24. {
  25.     cin >> n;
  26.  
  27.     for (int i = 1; i <= n; ++i)
  28.         cin >> a[i].x >> a[i].y >> a[i].z >> a[i].t;
  29. }
  30.  
  31. void Solve()
  32. {
  33.     sort(a + 1, a + n + 1);
  34.     // Sắp các hình chữ nhật tăng theo hoành độ và tung độ để duyệt tuần tự từ đầu tới cuối và cập nhật đáp án
  35.  
  36.     for (int i = 1; i <= n; ++i)
  37.     {
  38.         f[i] = 1;
  39.  
  40.         for (int j = 1; j < i; ++j)
  41.             if (a[i].x >= a[j].x && a[i].y >= a[j].x && a[i].z <= a[j].z && a[i].t <= a[j].t)
  42.                 f[i] = max(f[i], f[j] + 1);
  43.     }
  44.  
  45.     cout << *max_element(f + 1, f + n + 1);
  46. }
  47.  
  48. int32_t main()
  49. {
  50.     ios::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     cout.tie(0);
  53.     if (fopen(task ".INP", "r"))
  54.     {
  55.         freopen(task ".INP", "r", stdin);
  56.         freopen(task ".OUT", "w", stdout);
  57.     }
  58.  
  59.     Read();
  60.     Solve();
  61. }
  62.  
RAW Paste Data