fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define file(NAME) if (fopen(NAME".inp", "r")) freopen(NAME".inp", "r", stdin), freopen(NAME".out", "w", stdout)
  6. #define FOR(i, a, b) for (int i = (int) a; i <= (int) b; ++i)
  7. #define FOD(i, a, b) for (int i = (int) a; i >= (int) b; --i)
  8.  
  9. #define all(s) (s).begin(), (s).end()
  10. #define pb push_back
  11. #define ll long long
  12. #define fi first
  13. #define se second
  14. #define pii pair<int, int>
  15.  
  16. const int maxn = 105 + 5;
  17. const int N = 505;
  18. const int MOD = 1e9 + 7;
  19.  
  20. int n;
  21. pii a[maxn];
  22. int dp[maxn], trace[maxn];
  23.  
  24.  
  25.  
  26. signed main() {
  27. cin.tie(0) -> sync_with_stdio(0);
  28. file("x");
  29.  
  30. cin >> n;
  31.  
  32. FOR(i, 1, n) {
  33. cin >> a[i].fi >> a[i].se;
  34. }
  35.  
  36. sort(a + 1, a + n + 1);
  37.  
  38.  
  39. dp[1] = 1;
  40. FOR(i, 2, n) FOD(j, i - 1, 1) {
  41. if (a[i].se >= a[j].se && dp[i] < dp[j] + 1) {
  42. dp[i] = dp[j] + 1;
  43. trace[i] = j;
  44. }
  45. }
  46.  
  47.  
  48. int id = 0, ans = 0;
  49. FOR(i, 1, n) {
  50. if (ans < dp[i]) {
  51. ans = dp[i];
  52. id = i;
  53. }
  54. }
  55.  
  56. cout << ans << '\n';
  57.  
  58. vector<int> res;
  59. while (id) res.pb(id), id = trace[id];
  60.  
  61. reverse(all(res));
  62.  
  63. for (int x : res) cout << x << ' ';
  64. return 0;
  65. }
Success #stdin #stdout 0.01s 5264KB
stdin
12
1 1
3 5
3 7
5 2
6 7
7 6
8 3
9 10
10 4
11 6
12 5
13 9
stdout
6
1 4 7 9 11 12