SMMR-097: Crack

#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
const int N = 35;
char str[N+10];
int dp[N+10][N+10];
int mx, l;

set <string> ans;
bool p[N+10];
int complete;
void prt(int i, int j, int cnt){
    if(complete >= 200) return;
    if(cnt <= 0){
        string s;
        for(int idx=0;idx<l;idx++){
            if(p[idx]) s += str[idx];
        }
        if(ans.find(s) == ans.end()){
            ans.insert(s);
            complete ++;
        }
        return;
    }
    if(i > j) return;
    if(str[i-1] == str[j-1] and dp[i][j] == cnt){
        p[i-1] = p[j-1] = true;
        prt(i+1, j-1, cnt-2);
        p[i-1] = p[j-1] = false;
    }
    else{
        if(dp[i+1][j] == cnt)
            prt(i+1, j, cnt);
        if(dp[i][j-1] == cnt)
            prt(i, j-1, cnt);
    }
}

int f(int i, int j){
    if(i == j){
        return dp[i][j] = 1;
    }
    else if(i+1 == j and str[i-1] == str[j-1]){
        return dp[i][j] = 2;
    }
    if(dp[i][j] != 0) return dp[i][j];
    if(str[i-1] == str[j-1]){
        return dp[i][j] = f(i+1, j-1) + 2;
    }
    return dp[i][j] = max(f(i+1, j), f(i, j-1));
}

int main(){

    scanf("%s", str);
    l = strlen(str);

    for(int i=l;i>=1;i--){
        for(int j=i;j<=l;j++){
            if(i == j) dp[i][j] = 1;
            else if(i+1 == j and str[i-1] == str[j-1]) dp[i][j] = 2;
            else if(str[i-1] == str[j-1]) dp[i][j] = dp[i+1][j-1] + 2;
            else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }

    int mx = dp[1][l];

    prt(1, l, mx);

    for(auto i: ans) {
        cout << i << "\n";
    }

    return 0;
}
/**

CMUOCOM
= MOCOM

CMUOCCOCOMC
= CMOCCCOMC
= CMOCOCOMC

CMUO
= C
= M
= U
= O

COMUUMCO
*/