Reply Challenge Miner#4

#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()

const int maxn = 1500;
const int maxc = 52;

int n, C, q;

int dp[maxn+2][maxn+2][maxc];

void build() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int c = 0; c < maxc; ++c)
                dp[i][j][c] += dp[i][j - 1][c] + dp[i - 1][j][c] - dp[i - 1][j - 1][c];
}

bool ok(int l, int r, int t, int b) {
    int res = 0;
    for (int c = 0; c < maxc; ++c) {
        int k = dp[b][r][c] - dp[b][l - 1][c] - dp[t - 1][r][c] + dp[t - 1][l - 1][c];
        res += (bool)k;
    }
    return res == C;
}

void solve() {
    cin >> n >> C >> q;
    n += 1;

    for (int t = 0; t < q; ++t) {
        int i, j;
        char c;
        cin >> i >> j >> c;
        i += 1;
        j += 1;
        if (c >= 'a') c -= 6;
        c -= 'A';
        dp[i][j][(int)c] += 1;
    }
    build();

    int ans_l = 1;
    int ans_r = n;
    int ans_t = 1;
    int ans_b = n;
    int ans_s = 1e9;
    for (int t = 1; t <= n; ++t) {
        int b = t;
        while (b <= n && !ok(1, n, t, b)) b++;
        int s = b - t + 1;
        for (; b <= n; ++b) {
            int l = 1;
            for (int r = 1; r <= n; ++r) {
                s += b - t + 1;
                if (s >= ans_s) continue;

                while (l + 1 <= r && ok(l + 1, r, t, b)) {
                    l++;
                    s -= b - t + 1;
                }
                if (s < ans_s && ok(l, r, t, b)) {
                    ans_s = s;
                    ans_l = l;
                    ans_r = r;
                    ans_t = t;
                    ans_b = b;
                }
            }
        }
    }
    cout << ans_t - 1 << ' ' << ans_l - 1 << ' ' << ans_b - 1 << ' ' << ans_r - 1 << ' ' << ans_s << '\n';
    memset(dp, 0, sizeof dp);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        static int k = 0;
        cout << "Case #" << ++k << ": ";
        solve();
    }
}