Submission #1778949

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    string s;
    cin >> s;
    int n = s.length();
    
    vector<int> dp(n + 2, 0);
    vector<pair<int, char>> dp_pos(n + 1);
    
    map<char, int> next;
    for (char c = 'a'; c <= 'z'; ++c) next[c] = n;
    
    dp[n + 1] = 0;
    dp[n] = 1;
    repeat_reverse_from_to (i, n - 1, 0) {
        next[s[i]] = i;
        int m = n;
        for (char c = 'z'; c >= 'a'; --c) {
            if (dp[ next[c] + 1 ] <= m) {
                m = dp[ next[c] + 1 ] + 1;
                dp_pos[i].first = next[c] + 1;
                dp_pos[i].second = c;
            }
        }
        dp[i] = m + 1;
    }
    
    //repeat_from_to(i, 0, n) {cout << "dp_pos[" << i << "]=(" << dp_pos[i].first << "," << dp_pos[i].second << ")" << endl;}
    
    int pos = 0;
    while (pos < n) {
        cout << dp_pos[pos].second;
        pos = dp_pos[pos].first;
    }
    cout << endl;
}

Submission Info

Judge Result