• Source
    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. }