제출 #1109769

#제출 시각아이디문제언어결과실행 시간메모리
1109769Kirill22최솟값 배열 (IZhO11_hyper)C++17
100 / 100
1042 ms64072 KiB
#include "bits/stdc++.h"

using namespace std;

const int N = 35;
int n, m;
int a[N][N][N][N][6];

void solve() {
    cin >> n >> m;
    assert(n <= N);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    cin >> a[i][j][x][y][0];
                }
            }
        }
    }
    for (int d = 1; d < 6; d++) {
        int step = (1 << d) / 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int x = 0; x < n; x++) {
                    for (int y = 0; y < n; y++) {
                        if (max({i, j, x, y}) + (1 << d) <= n) {
                            a[i][j][x][y][d] = a[i][j][x][y][d - 1];
                            for (auto i2 : vector<int> {i, i + step}) for (auto j2 : vector<int> {j, j + step}) {
                                for (auto x2 : vector<int> {x, x + step}) for (auto y2 : vector<int> {y, y + step}) {
                                    a[i][j][x][y][d] = min(a[i][j][x][y][d], a[i2][j2][x2][y2][d - 1]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i + m <= n; i++) {
        for (int j = 0; j + m <= n; j++) {
            for (int x = 0; x + m <= n; x++) {
                for (int y = 0; y + m <= n; y++) {
                    int d = 6;
                    while ((1 << d) > m) {
                        d--;
                    }
                    int ans = a[i][j][x][y][d];
                    int step = m - (1 << d);
                    for (auto i2 : vector<int> {i, i + step}) for (auto j2 : vector<int> {j, j + step}) {
                        for (auto x2 : vector<int> {x, x + step}) for (auto y2 : vector<int> {y, y + step}) {
                                ans = min(ans, a[i2][j2][x2][y2][d]);
                            }
                    }
                    cout << ans << " ";
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...