2802번: 크레용

https://www.acmicpc.net/problem/2802

#include<stdio.h>
#include<algorithm>
using namespace std;
int x[100000], y[100000], z[100000], s[257][257][257], n, cnt;
int f(int x1, int y1, int z1, int x2, int y2, int z2) {
    return s[x2][y2][z2] - s[x1 - 1][y2][z2] - s[x2][y1 - 1][z2] - s[x2][y2][z1 - 1]
        + s[x2][y1 - 1][z1 - 1] + s[x1 - 1][y2][z1 - 1] + s[x1 - 1][y1 - 1][z2] - s[x1 - 1][y1 - 1][z1 - 1];
}
int main() {
    scanf("%d %d", &n, &cnt);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &x[i], &y[i], &z[i]);
        s[x[i] + 1][y[i] + 1][z[i] + 1]++;
    }
    for (int i = 1; i <= 256; i++)
        for (int j = 1; j <= 256; j++)
            for (int k = 1; k <= 256; k++)
                s[i][j][k] += s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1]
                - s[i][j - 1][k - 1] - s[i - 1][j][k - 1] - s[i - 1][j - 1][k]
                + s[i - 1][j - 1][k - 1];
    int h = 0, t = 255, m, tx, ty, tz;
    while (h <= t) {
        m = (h + t) / 2;
        for (int i = 1; i <= 256 - m; i++)
            for (int j = 1; j <= 256 - m; j++)
                for (int k = 1; k <= 256 - m; k++)
                    if (f(i, j, k, i + m, j + m, k + m) >= cnt)
                        t = m - 1, tx = i - 1, ty = j - 1, tz = k - 1;
        if (t != m - 1) h = m + 1;
    }
    printf("%d\n", h);
    for (int i = 0; i < n; i++) {
        if (cnt&&tx <= x[i] && x[i] <= tx + h
            &&ty <= y[i] && y[i] <= ty + h
            &&tz <= z[i] && z[i] <= tz + h)
            printf("%d %d %d\n", x[i], y[i], z[i]), cnt--;
    }
    return 0;
}