#include <bits/stdc++.h>
#define int long long
using namespace std;
#define file ""
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return l + rd() % (r - l + 1);
}
const int N = 40;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 2e9;
const long long ooo = 1e18;
template<class X, class Y> bool mini(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int n, m;
int f[N][N][N][N][7];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
for (int l = 1; l <= n; ++l)
cin >> f[i][j][k][l][0];
for (int s = 1; s <= 6; ++s) {
int x = bit(s - 1);
int y = n - bit(s) + 1;
for (int i = 1; i <= y; ++i)
for (int j = 1; j <= y; ++j)
for (int k = 1; k <= y; ++k)
for (int l = 1; l <= y; ++l) {
for (int mask = 0; mask < bit(4); ++mask) {
int ni = i + getbit(mask, 0) * x;
int nj = j + getbit(mask, 1) * x;
int nk = k + getbit(mask, 2) * x;
int nl = l + getbit(mask, 3) * x;
mini(f[i][j][k][l][s], f[ni][nj][nk][nl][s - 1]);
}
}
}
auto get = [&] (int i, int j, int k, int l, int ri, int rj, int rk, int rl) {
int res = ooo;
int s = log2(m);
for (int mask = 0; mask < bit(4); ++mask) {
int ii = getbit(mask, 0) ? ri - bit(s) + 1 : i;
int jj = getbit(mask, 1) ? rj - bit(s) + 1 : j;
int kk = getbit(mask, 2) ? rk - bit(s) + 1 : k;
int ll = getbit(mask, 3) ? rl - bit(s) + 1 : l;
mini(res, f[ii][jj][kk][ll][s]);
}
return res;
};
for (int i = 1; i <= n - m + 1; ++i)
for (int j = 1; j <= n - m + 1; ++j)
for (int k = 1; k <= n - m + 1; ++k)
for (int l = 1; l <= n - m + 1; ++l) {
int ri = min(n, i + m - 1);
int rj = min(n, j + m - 1);
int rk = min(n, k + m - 1);
int rl = min(n, l + m - 1);
cout << get(i, j, k, l, ri, rj, rk, rl) << ' ';
}
return 0;
}
/*
3 2
3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4
4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5
-1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3
-2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1
-5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2
-4 -3 1 3 1
-5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
5 ms |
29016 KB |
Output is correct |
| 5 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 6 |
Correct |
17 ms |
49752 KB |
Output is correct |
| 7 |
Correct |
16 ms |
49788 KB |
Output is correct |
| 8 |
Correct |
42 ms |
70208 KB |
Output is correct |
| 9 |
Correct |
58 ms |
71748 KB |
Output is correct |
| 10 |
Correct |
41 ms |
70208 KB |
Output is correct |
| 11 |
Correct |
105 ms |
89168 KB |
Output is correct |
| 12 |
Correct |
206 ms |
108172 KB |
Output is correct |
| 13 |
Correct |
200 ms |
107144 KB |
Output is correct |
| 14 |
Correct |
254 ms |
112780 KB |
Output is correct |
| 15 |
Incorrect |
410 ms |
128912 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
