anon20016

M

Nov 22nd, 2019
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9.  
  10. #define ull unsigned long long
  11. #define ll long long
  12.  
  13. using namespace std;
  14.  
  15.  
  16. int main() {
  17.     //freopen("input.txt", "r", stdin);
  18.     //freopen("output.txt", "w", stdout);
  19.     int n;
  20.     cin >> n;
  21.     vector<int> a(n);
  22.     for (int i = 0; i < n; i++) {
  23.         cin >> a[i];
  24.     }
  25.     vector<int> d(n, 1);
  26.     vector<int> p(n, -1);
  27.     for (int i = 0; i < n; i++) {
  28.         for (int j = 0; j < i; j++) {
  29.             if (a[j] >= a[i]) {
  30.                 if (d[i] < d[j] + 1) {
  31.                     p[i] = j;
  32.                     d[i] = d[j] + 1;
  33.                 }
  34.             }
  35.         }
  36.     }
  37.     int ans = 0;
  38.     for (int i = 0; i < n; i++) {
  39.         if (d[i] > d[ans]) {
  40.             ans = i;
  41.         }
  42.     }
  43.     if (d[ans] <= 1) {
  44.         cout << 0;
  45.         return 0;
  46.     }
  47.     vector<int> r;
  48.     cout << d[ans] << endl;
  49.     while (p[ans] != -1) {
  50.         r.push_back(ans + 1);
  51.         ans = p[ans];
  52.     }
  53.     r.push_back(ans + 1);
  54.     for (int i = r.size() - 1; i >= 0; i--) {
  55.         cout << r[i] << endl;
  56.     }
  57.    
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment