fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     string s;
  7.     cin >> s;
  8.  
  9.     int n = s.size();
  10.     vector<int> f(n, 1);
  11.     for (int i = n - 2; i >= 0; --i) {
  12.         for (int j = i + 1; j < n; ++j) {
  13.             if (s[j] < s[i]) {
  14.                 f[i] = max(f[i], 1 + f[j]);
  15.             }
  16.         }
  17.     }
  18.  
  19.     int cur = 0;
  20.     for (int x : f) cur = max(cur, x);
  21.  
  22.     string ans = "";
  23.     int last = -1;
  24.     char pre = '9' + 1;
  25.  
  26.     for (int k = cur; k > 0; --k) {
  27.         char mxchar = '0'-1;
  28.         int j = -1;
  29.  
  30.         for (int i = last + 1; i < n; ++i) {
  31.  
  32.             if (s[i] < pre && f[i] >= k) {
  33.                 if (s[i] > mxchar) {
  34.                     mxchar = s[i];
  35.                     j = i;
  36.                 }
  37.             }
  38.         }
  39.  
  40.         if (j != -1) {
  41.             ans += mxchar;
  42.             last = j;
  43.             pre = mxchar;
  44.         }
  45.     }
  46.  
  47.     cout << ans;
  48.  
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iGo5zo
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!