제출 #683897

#제출 시각아이디문제언어결과실행 시간메모리
683897KiriLL1ca최솟값 배열 (IZhO11_hyper)C++17
100 / 100
406 ms65392 KiB
#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)

using namespace std;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef pair <int, int> pii;

const int N = 40;

int a[N][N][N][N], res[N][N][N][N];
int st[7][N][N][N][N];
int lg[N];

inline int ask (int i, int j, int k, int l, int ri, int rj, int rk, int rl, int m) {
        int s = lg[m];
        int ii = ri - (1 << s) + 1;
        int jj = rj - (1 << s) + 1;
        int kk = rk - (1 << s) + 1;
        int ll = rl - (1 << s) + 1;

        return min({
                   st[s][i][j][k][l],
                   st[s][ii][j][k][l],
                   st[s][i][jj][k][l],
                   st[s][i][j][kk][l],
                   st[s][i][j][k][ll],

                   st[s][ii][jj][k][l],
                   st[s][ii][j][kk][l],
                   st[s][ii][j][k][ll],

                   st[s][i][jj][kk][l],
                   st[s][i][jj][k][ll],

                   st[s][i][j][kk][ll],

                   st[s][ii][jj][kk][l],
                   st[s][ii][jj][k][ll],
                   st[s][ii][j][kk][ll],
                   st[s][i][jj][kk][ll],

                   st[s][ii][jj][kk][ll]
                   });
}

inline void solve () {
        for (int i = 2; i < N; ++i) lg[i] = lg[i >> 1] + 1;

        int n, M; cin >> n >> M;
        forn (i, 1, n) forn (j, 1, n) forn (k, 1, n) forn (l, 1, n) cin >> a[i][j][k][l];
        forn (i, 1, n) forn (j, 1, n) forn (k, 1, n) forn (l, 1, n) st[0][i][j][k][l] = a[i][j][k][l];

        for (int s = 1; s <= 6; ++s) {
                int p = (1 << (s - 1));
                int G = n - (1 << s) + 1;
                forn (i, 1, G) forn (j, 1, G) forn (k, 1, G) forn (l, 1, G) {
                        st[s][i][j][k][l] = min({
                                                st[s - 1][i + 0][j + 0][k + 0][l + 0],
                                                st[s - 1][i + p][j + 0][k + 0][l + 0],
                                                st[s - 1][i + 0][j + p][k + 0][l + 0],
                                                st[s - 1][i + 0][j + 0][k + p][l + 0],
                                                st[s - 1][i + 0][j + 0][k + 0][l + p],

                                                st[s - 1][i + p][j + p][k + 0][l + 0],
                                                st[s - 1][i + p][j + 0][k + p][l + 0],
                                                st[s - 1][i + p][j + 0][k + 0][l + p],

                                                st[s - 1][i + 0][j + p][k + p][l + 0],
                                                st[s - 1][i + 0][j + p][k + 0][l + p],

                                                st[s - 1][i + 0][j + 0][k + p][l + p],

                                                st[s - 1][i + p][j + p][k + p][l + 0],
                                                st[s - 1][i + p][j + p][k + 0][l + p],
                                                st[s - 1][i + p][j + 0][k + p][l + p],
                                                st[s - 1][i + 0][j + p][k + p][l + p],

                                                st[s - 1][i + p][j + p][k + p][l + p],
                                                });
                }
        }

        int G = n - M + 1;
        forn (i, 1, G) forn (j, 1, G) forn (k, 1, G) forn (l, 1, G) {
                cout << ask(i,         j,         k,         l,
                            i + M - 1, j + M - 1, k + M - 1, l + M - 1, M) << " ";
        }

}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #else
                
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...