C++ source, ASCII text
1
#include <iostream>
2
#include <vector>
3
using std::vector;
5
template <typename T>
7
inline T safe_get(vector<vector<T>> const &a, int const i, int const j) {
8
if (i < 0 || a.size() <= i || j < 0 || a[0].size() <= j) {
9
return 0;
10
}
11
return a[i][j];
12
}
13
inline long long int get_ps(vector<vector<long long int>> const &ps,
15
int const i0, int const j0,
16
int const i1, int const j1) {
17
return safe_get(ps, i1, j1)
18
- safe_get(ps, i0-1, j1)
19
- safe_get(ps, i1, j0-1)
20
+ safe_get(ps, i0-1, j0-1);
21
}
22
int main() {
24
using std::cin, std::cout;
25
int N, M;
27
long long int K;
28
cin >> N >> M >> K;
29
vector<vector<int>> mat(N, vector<int>(M));
30
for (int i=0; i<N; i++) {
31
for (int j=0; j<M; j++) {
32
cin >> mat[i][j];
33
}
34
}
35
vector<vector<long long int>> ps(N, vector<long long int>(M));
36
for(int i=0;i<N;i++){
37
for(int j=0;j<M;j++){
38
ps[i][j] = safe_get(ps, i-1, j) + safe_get(ps, i, j-1)
39
- safe_get(ps, i-1, j-1) + mat[i][j];
40
}
41
}
42
vector<vector<int>> min_size(N, vector<int>(M));
43
for (int i = 0; i < N; ++i) {
44
for (int j = 0; j < M; ++j) {
45
int const prev_size = std::max(
46
std::max(
47
safe_get(min_size, i-1, j),
48
safe_get(min_size, i, j-1)
49
),
50
3
51
);
52
int size = (prev_size-1) / 2 - 1;
53
long long int sum = get_ps(ps, i-size, j-size, i+size, j+size);
54
while (sum < K && i - (size+1) >= 0 && j - (size+1) >= 0 && i + (size+1) < N && i + (size+1) < M) {
55
++size;
56
sum = get_ps(ps, i-size, j-size, i+size, j+size);
57
}
58
if (sum < K) {
59
min_size[i][j] = -1;
60
} else {
61
min_size[i][j] = 2*size+1;
62
}
63
}
64
}
65
for (int i = 0; i < N; ++i) {
67
for (int j = 0; j < M; ++j) {
68
cout << min_size[i][j] << ' ';
69
}
70
cout << '\n';
71
}
72
return 0;
73
}
74