1189A - Keanu Reeves - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 110;

bool dp[MAXN][MAXN];
int last[MAXN][MAXN];
int s[MAXN];
char c[MAXN];

void printans(int k, int n){
    if(n == 0) return;
    int j = last[k][n];
    printans(k - 1, j - 1);
    for(int i = j; i <= n; i++){
        printf("%d", s[i]);
    }
    printf(" ");
}

int main(){
    int n; scanf("%d", &n);
    scanf(" %s", c);
    for(int i = 0; i < n; i++){
        s[i + 1] = c[i] - '0';
    }

    for(int i = 0; i <= n; i++) dp[i][i] = true;

    for(int i = 1; i <= n; i++){
        for(int k = 1; k <= i; k++){
            int qtd0 = 0, qtd1 = 0;
            for(int j = i; j >= 1; j--){
                if(s[j] == 0) qtd0++;
                if(s[j] == 1) qtd1++;
                if(qtd0 == qtd1) continue;
                if(dp[k - 1][j - 1]){
                    dp[k][i] = true;
                    last[k][i] = j;
                    break;
                }
            }
        }
    }

    for(int k = 1; k <= n; k++){
        if(dp[k][n]){
            printf("%d\n", k);
            printans(k, n);
            return 0;
        }
    }
}