#include <iostream>
#include <vector>
#include <complex>
using namespace std;
using ll = long long;
const complex<int> IMAG(0, 1);
vector<vector<int>> special;
vector<vector<int>> used;
vector<vector<int>> f;
int unfill(int i, int j){
--used[i][j];
return -f[i][j];
}
int fill(int i, int j){
++used[i][j];
return f[i][j];
}
int fill_plus(int i, int j){
int ans = fill(i, j);
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
ans += fill(i + mv.real(), j + mv.imag());
}
special[i][j] = 0;
return ans;
}
int dfs(int i, int j){
if(special[i][j]){
int ans = 0;
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
if(used[i + mv.real()][j + mv.imag()]){
ans += unfill(i + mv.real(), j + mv.imag());
break;
}
}
ans += fill_plus(i, j);
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
ans += dfs(i + mv.real(), j + mv.imag());
}
return ans;
} else {
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
return dfs(i + mv.real(), j + mv.imag());
}
}
return 0;
}
}
complex<int> mindfs(int i, int j){
complex<int> ans = i + 1 + j * IMAG;
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
if(f[ans.real()][ans.imag()] > f[i + mv.real()][j + mv.imag()]){
ans = mv + i + j * IMAG;
}
}
special[i][j] = 2;
for(complex<int> timer = 0, mv = 1; timer != 4; timer += 1, mv *= IMAG){
if(special[i + mv.real() * 2][j + mv.imag() * 2] == 1){
complex<int> nans = mindfs(i + mv.real() * 2, j + mv.imag() * 2);
if(f[ans.real()][ans.imag()] > f[nans.real()][nans.imag()]){
ans = nans;
}
}
}
return ans;
}
signed main(){
int n, m;
cin >> n >> m;
f.assign(n + 2, vector<int>(m + 2));
used.assign(n + 2, vector<int>(m + 2));
special.assign(n + 2, vector<int>(m + 2));
for(int i = 0; i <= n + 1; ++i)
used[i][0] = used[i][m + 1] = 1;
for(int j = 0; j <= m + 1; ++j)
used[0][j] = used[n + 1][j] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
cin >> f[i][j];
}
}
int q;
cin >> q;
for(int i = 0; i < q; ++i){
int x, y;
cin >> x >> y;
++x, ++y;
special[x][y] = 1;
}
ll ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(!special[i][j])
continue;
if(special[i + 1][j]){
ans += fill_plus(i, j);
ans += unfill(i + 1, j);
ans += fill_plus(i + 1, j);
ans += unfill(i, j);
}
if(special[i][j + 1]){
ans += fill_plus(i, j);
ans += unfill(i, j + 1);
ans += fill_plus(i, j + 1);
ans += unfill(i, j);
}
if(special[i + 1][j + 1]){
ans += fill_plus(i, j);
ans += unfill(i, j + 1);
ans += fill_plus(i + 1, j + 1);
ans += unfill(i + 1, j);
}
if(special[i - 1][j + 1]){
ans += fill_plus(i, j);
ans += unfill(i, j + 1);
ans += fill_plus(i - 1, j + 1);
ans += unfill(i - 1, j);
}
}
}
for(int i = 0; i <= n + 1; ++i){
for(int j = 0; j <= m + 1; ++j){
if(used[i][j]){
ans += dfs(i, j);
}
}
}
//for(int i = 0; i <= n + 1; ++i){
//for(int j = 0; j <= m + 1; ++j){
//cout << used[i][j] << ' ';
//}
//cout << endl;
//}
//cout << ans << endl;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if(special[i][j]){
complex<int> pt = mindfs(i, j);
used[pt.real()][pt.imag()] = 1;
ans += dfs(pt.real(), pt.imag());
}
}
}
for(int i = 0; i <= n + 1; ++i){
for(int j = 0; j <= m + 1; ++j){
if(used[i][j] > 1){
cout << "No\n";
return 0;
}
}
}
cout << ans << endl;
}
Compilation message
covering.cpp: In function 'int dfs(int, int)':
covering.cpp:47:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
| ~~~~~~~~~~~~~~^~~~~~~~~~
covering.cpp:47:91: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(0 < i + mv.real() && i + mv.real() < f.size() && 0 < j + mv.imag() && j + mv.imag() < f[0].size() && special[i + mv.real()][j + mv.imag()]){
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
588 KB |
Output is correct |
3 |
Correct |
26 ms |
1864 KB |
Output is correct |
4 |
Correct |
78 ms |
4896 KB |
Output is correct |
5 |
Correct |
255 ms |
13220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
10 ms |
684 KB |
Output is correct |
3 |
Correct |
26 ms |
1868 KB |
Output is correct |
4 |
Correct |
79 ms |
5008 KB |
Output is correct |
5 |
Correct |
260 ms |
13336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
672 KB |
Output is correct |
3 |
Correct |
26 ms |
1880 KB |
Output is correct |
4 |
Correct |
77 ms |
4992 KB |
Output is correct |
5 |
Correct |
258 ms |
13348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
16 ms |
1120 KB |
Output is correct |
4 |
Correct |
8 ms |
844 KB |
Output is correct |
5 |
Correct |
27 ms |
2124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
588 KB |
Output is correct |
3 |
Correct |
26 ms |
1864 KB |
Output is correct |
4 |
Correct |
78 ms |
4896 KB |
Output is correct |
5 |
Correct |
255 ms |
13220 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
684 KB |
Output is correct |
8 |
Correct |
26 ms |
1868 KB |
Output is correct |
9 |
Correct |
79 ms |
5008 KB |
Output is correct |
10 |
Correct |
260 ms |
13336 KB |
Output is correct |
11 |
Correct |
4 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
672 KB |
Output is correct |
13 |
Correct |
26 ms |
1880 KB |
Output is correct |
14 |
Correct |
77 ms |
4992 KB |
Output is correct |
15 |
Correct |
258 ms |
13348 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
16 ms |
1120 KB |
Output is correct |
19 |
Correct |
8 ms |
844 KB |
Output is correct |
20 |
Correct |
27 ms |
2124 KB |
Output is correct |
21 |
Correct |
3 ms |
460 KB |
Output is correct |
22 |
Correct |
8 ms |
716 KB |
Output is correct |
23 |
Correct |
27 ms |
1868 KB |
Output is correct |
24 |
Correct |
77 ms |
4932 KB |
Output is correct |
25 |
Correct |
261 ms |
13268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
588 KB |
Output is correct |
3 |
Correct |
26 ms |
1864 KB |
Output is correct |
4 |
Correct |
78 ms |
4896 KB |
Output is correct |
5 |
Correct |
255 ms |
13220 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
684 KB |
Output is correct |
8 |
Correct |
26 ms |
1868 KB |
Output is correct |
9 |
Correct |
79 ms |
5008 KB |
Output is correct |
10 |
Correct |
260 ms |
13336 KB |
Output is correct |
11 |
Correct |
4 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
672 KB |
Output is correct |
13 |
Correct |
26 ms |
1880 KB |
Output is correct |
14 |
Correct |
77 ms |
4992 KB |
Output is correct |
15 |
Correct |
258 ms |
13348 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
16 ms |
1120 KB |
Output is correct |
19 |
Correct |
8 ms |
844 KB |
Output is correct |
20 |
Correct |
27 ms |
2124 KB |
Output is correct |
21 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |