E题能过样例交上去0分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 1 << 9;
const int MAXK = 82;
int dp[MAXN][MAXM][MAXK][MAXN];// ¨¨¡À¨º¡ì¦Ì??¦Ì
//¦Ì¨²iDD ¦Ì¡À?¡ãDD¡Á¡ä¨¬??aj ¡¤???¨¢?K??¨¤¡Á ¨°?DD¨®DN?? 
int from[MAXN][MAXM][MAXK][MAXN];// ¡ä¨®??¨¤?¨¤¡ä
int sum[MAXM];//¡Á¡ä¨¬??ak ¨®D?¨¤¨¦¨´¨¤¡Á
void work() {
    int n, m, k;
    std::cin >> n >> m >> k;
    int result = INT_MAX;
    int idx = 91;
    for (int i = 0; i < (1 << m); i++) {
        int val = dp[n][i][k][m] + 3 * sum[i];
        val -= (i & 1) + (i >> (m - 1) & 1);
        if (val < result) {
            result = val;
            idx = i;
        }
    }
    cout << 8 * k - result << endl;
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < m; j++) {
            if (idx >> j & 1) {
                cout << "*";
            }
            else {
                cout << ".";
            }
        } cout << endl;
        k -= sum[idx];
        idx = from[i][idx][k][m];
    }
}
unsigned _builtin_popcount(unsigned u) {
    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
    return u;
}
int main() {
    for (int i = 0; i < (1 << 9); i++) {
        sum[i] = _builtin_popcount(i);
    }
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= 9; i++) {
        dp[0][(1 << i) - 1][0][i] = 0;
        for (int j = 1; j <= 9; j++) {
            for (int now = 0; now < (1 << i); now++) {
                for (int last = 0; last < (1 << i); last++) {
                    for (int w = 0; w < (j - 1) * i + 1; w++) {
                        int new_k = w + sum[now];
                        int val = dp[j - 1][last][w][i];
                        if (j > 1) {
                            //¨®?¨¦?¨°?DD¦Ì?1¡À?¡Á
                            val += sum[now & last] * 2 + sum[now & (last >> 1)] * 2
                                + sum[now & (last << 1)] * 2;
                        }
                        else {
                            //¨®?¨¦?¡À???¦Ì?1¡À?¡Á
                            val += sum[now] * 3;
                        }
                        val += sum[now & (now >> 1)] * 2;//¡Á¨®¨®¨°
                        val += (now & 1) * 2 + ((now >> (i - 1)) & 1) * 2;//¡À???
                        if (dp[j][now][new_k][i] > val) {
                            dp[j][now][new_k][i] = val;
                            from[j][now][new_k][i] = last;
                        }
                    }
                }
            }
        }
    }
    int T; std::cin >> T;
    while (T--) {
        work();
    }
    return 0;
}