#include <iostream>
#include <vector>
#include <complex>
using namespace std;
using ll = long long;
const complex<int> IMAG(0, 1);
vector<vector<ll>> special;
vector<vector<ll>> used;
vector<vector<ll>> f;
ll unfill(ll i, ll j){
--used[i][j];
return -f[i][j];
}
ll fill(ll i, ll j){
++used[i][j];
return f[i][j];
}
ll fill_plus(ll i, ll j){
ll 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;
}
ll dfs(ll i, ll j){
if(special[i][j]){
ll 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(){
ll n, m;
cin >> n >> m;
f.assign(n + 2, vector<ll>(m + 2));
used.assign(n + 2, vector<ll>(m + 2));
special.assign(n + 2, vector<ll>(m + 2));
for(ll i = 0; i <= n + 1; ++i)
used[i][0] = used[i][m + 1] = 1;
for(ll j = 0; j <= m + 1; ++j)
used[0][j] = used[n + 1][j] = 1;
for(ll i = 1; i <= n; ++i){
for(ll j = 1; j <= m; ++j){
cin >> f[i][j];
}
}
ll q;
cin >> q;
for(ll i = 0; i < q; ++i){
ll x, y;
cin >> x >> y;
++x, ++y;
special[x][y] = 1;
}
ll ans = 0;
for(ll i = 1; i <= n; ++i){
for(ll 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(ll i = 0; i <= n + 1; ++i){
for(ll j = 0; j <= m + 1; ++j){
if(used[i][j]){
ans += dfs(i, j);
}
}
}
//for(ll i = 0; i <= n + 1; ++i){
//for(ll j = 0; j <= m + 1; ++j){
//cout << used[i][j] << ' ';
//}
//cout << endl;
//}
//cout << ans << endl;
for(ll i = 1; i <= n; ++i){
for(ll 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(ll i = 0; i <= n + 1; ++i){
for(ll 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 'll dfs(ll, ll)':
covering.cpp:47:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long 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: 'll' {aka 'long long int'} and 'std::vector<long long 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 |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
972 KB |
Output is correct |
3 |
Correct |
25 ms |
2636 KB |
Output is correct |
4 |
Correct |
79 ms |
7372 KB |
Output is correct |
5 |
Correct |
280 ms |
23968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
1048 KB |
Output is correct |
3 |
Correct |
26 ms |
2636 KB |
Output is correct |
4 |
Correct |
86 ms |
7456 KB |
Output is correct |
5 |
Correct |
266 ms |
23976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
9 ms |
1056 KB |
Output is correct |
3 |
Correct |
26 ms |
2680 KB |
Output is correct |
4 |
Correct |
96 ms |
7372 KB |
Output is correct |
5 |
Correct |
261 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
13 ms |
1612 KB |
Output is correct |
4 |
Correct |
9 ms |
1156 KB |
Output is correct |
5 |
Correct |
33 ms |
3148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
972 KB |
Output is correct |
3 |
Correct |
25 ms |
2636 KB |
Output is correct |
4 |
Correct |
79 ms |
7372 KB |
Output is correct |
5 |
Correct |
280 ms |
23968 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
8 ms |
1048 KB |
Output is correct |
8 |
Correct |
26 ms |
2636 KB |
Output is correct |
9 |
Correct |
86 ms |
7456 KB |
Output is correct |
10 |
Correct |
266 ms |
23976 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
9 ms |
1056 KB |
Output is correct |
13 |
Correct |
26 ms |
2680 KB |
Output is correct |
14 |
Correct |
96 ms |
7372 KB |
Output is correct |
15 |
Correct |
261 ms |
23884 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
13 ms |
1612 KB |
Output is correct |
19 |
Correct |
9 ms |
1156 KB |
Output is correct |
20 |
Correct |
33 ms |
3148 KB |
Output is correct |
21 |
Correct |
3 ms |
460 KB |
Output is correct |
22 |
Correct |
8 ms |
972 KB |
Output is correct |
23 |
Correct |
26 ms |
2692 KB |
Output is correct |
24 |
Correct |
79 ms |
7372 KB |
Output is correct |
25 |
Correct |
261 ms |
23884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
460 KB |
Output is correct |
2 |
Correct |
8 ms |
972 KB |
Output is correct |
3 |
Correct |
25 ms |
2636 KB |
Output is correct |
4 |
Correct |
79 ms |
7372 KB |
Output is correct |
5 |
Correct |
280 ms |
23968 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
8 ms |
1048 KB |
Output is correct |
8 |
Correct |
26 ms |
2636 KB |
Output is correct |
9 |
Correct |
86 ms |
7456 KB |
Output is correct |
10 |
Correct |
266 ms |
23976 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
9 ms |
1056 KB |
Output is correct |
13 |
Correct |
26 ms |
2680 KB |
Output is correct |
14 |
Correct |
96 ms |
7372 KB |
Output is correct |
15 |
Correct |
261 ms |
23884 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
13 ms |
1612 KB |
Output is correct |
19 |
Correct |
9 ms |
1156 KB |
Output is correct |
20 |
Correct |
33 ms |
3148 KB |
Output is correct |
21 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |