#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
/*
dp[k][i] = can the kth block of black cells end at position i
dp[k][i] |= dp[k-1][j]
if j < i-C[k]
and [j+1, i-C[k]] has no black cells
and [i-C[k]+1, i] has no white cells
dp[K][i] is valid if no black cells after i
*/
string solve_puzzle(string S, vector<int> C) {
int N = S.size(), K = C.size();
vector<int> pX(N+1), p_(N+1), canX(N), canY(N);
for(int i = 1; i <= N; i++) {
pX[i] += pX[i-1] + (S[i-1] == 'X');
p_[i] += p_[i-1] + (S[i-1] == '_');
}
auto qX = [&](int l, int r) {
if (!l) return pX[r];
return pX[r] - pX[l-1];
};
auto q_ = [&](int l, int r) {
if (!l) return p_[r];
return p_[r] - p_[l-1];
};
vector<vector<int>> dp(K+1, vector<int>(N+1));
for(int i = 0; i <= N; i++) dp[0][i] = qX(0, i) == 0;
for(int k = 1; k <= K; k++) {
for(int i = 1; i <= N; i++) {
if (i-C[k-1] == 0 && k == 1) {
dp[k][i] = 1;
}
for(int j = 0; j < i-C[k-1]; j++) {
if (!qX(j+1, i-C[k-1]) && !q_(i-C[k-1]+1, i)) dp[k][i] |= dp[k-1][j];
}
if (k == K) dp[k][i] &= !qX(i+1, N);
// cout << k-1 << ' ' << i-1 << ' ' << dp[k][i] << endl;
}
}
return "";
}
