fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. const ll INF = (ll)1e18;
  9.  
  10. int main() {
  11. int n;
  12. ll k;
  13. cin >> n >> k;
  14. vector<int> a(n);
  15. for (int i = 0; i < n; ++i) cin >> a[i];
  16.  
  17. vector<ll> dp(n, 1); // dp[i] — количество возрастающих подпоследовательностей, начинающихся с i
  18.  
  19. // Считаем dp[i] — начиная с конца
  20. for (int i = n - 1; i >= 0; --i) {
  21. for (int j = i + 1; j < n; ++j) {
  22. if (a[j] > a[i]) {
  23. dp[i] += dp[j];
  24. if (dp[i] >= INF) dp[i] = INF;
  25. }
  26. }
  27. }
  28.  
  29. vector<int> result;
  30. ll remaining_k = k;
  31. int last = INT_MIN;
  32.  
  33. int pos = 0;
  34. while (remaining_k > 0 && pos < n) {
  35. for (int i = pos; i < n; ++i) {
  36. if (a[i] <= last) continue;
  37.  
  38. // считаем сколько последовательностей начинается с i, и соответствуют условиям
  39. ll count = dp[i];
  40.  
  41. if (remaining_k > count) {
  42. remaining_k -= count;
  43. } else {
  44. result.push_back(a[i]);
  45. last = a[i];
  46. pos = i + 1;
  47. remaining_k--; // одна подпоследовательность выбрана
  48. break;
  49. }
  50. }
  51. }
  52.  
  53. cout << result.size() << endl;
  54. for (int x : result) cout << x << " ";
  55. cout << endl;
  56.  
  57. return 0;
  58. }
Success #stdin #stdout 0.01s 5288KB
stdin
3 2
1 1 2
stdout
2
1 2