#include "bits/stdc++.h"
using namespace std;
#define arr array<int, 2>
void solve(){
int n, m; cin>>n>>m;
vector<vector<int>> a(n, vector<int>(m));
vector<vector<int>> used(n, vector<int>(m));
vector<vector<int>> is(n, vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
int k; cin>>k;
vector<array<int, 2>> cc(k);
for(int i=0;i<k;i++){
cin>>cc[i][0]>>cc[i][1];
}
for(int i=0;i<k;i++){
is[cc[i][0]][cc[i][1]] = 1;
}
int ch[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int ch2[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
for(int i=0;i<k;i++){
is[cc[i][0]][cc[i][1]] = 1;
}
int res = 0;
auto check = [&](int i, int j) -> bool{
return (~i && i < n && ~j && j < m);
};
vector<arr> nw;
set<arr> ss;
for(int t=0;t<k;t++){
int i = cc[t][0], j = cc[t][1], cnt = 0;
int sum = a[i][j];
vector<array<int, 3>> aa;
for(int t=0;t<4;t++){
int x = i + ch[t][0], y = j + ch[t][1];
if(!check(x, y)) cnt++;
else if(is[x][y]) cnt++;
else sum += a[x][y], aa.push_back({x, y, a[x][y]});
}
int cnt2 = 0;
for(int t=0;t<4;t++){
int x = i + ch2[t][0], y = j + ch2[t][1];
if(!check(x, y)) continue;
else if(is[x][y]) cnt2++;
}
if(cnt2 > 1 || cnt > 1 || (cnt && cnt2)){
cout<<"No\n";
return;
} if(cnt){
res = res + sum;
used[i][j] = 1;
for(auto x : aa) used[x[0]][x[1]] = 1;
} else if(cnt2){
res += a[cc[t][0]][cc[t][1]];
for(auto x : aa){
if(ss.count({x[0], x[1]})) continue;
res += x[2];
ss.insert({x[0], x[1]});
used[x[0]][x[1]] = 1;
} used[i][j] = 1;
} else nw.push_back(cc[t]);
}
int ch3[4][2] = {{0, -2}, {0, 2}, {2, 0}, {-2, 0}};
k = (int)nw.size();
vector<vector<vector<arr>>> edges(n, vector<vector<arr>>(m));
for(int t=0;t<k;t++){
int i = nw[t][0], j = nw[t][1];
for(int t=0;t<4;t++){
int x = i + ch3[t][0], y = j + ch3[t][1];
if(!check(x, y)) continue;
if(is[x][y] && !used[x][y]) edges[i][j].push_back({x, y});
}
}
int cntv, sum, mn, cnt;
function<void(int, int)> dfs = [&](int i, int j) -> void{
used[i][j] = 1; sum += a[i][j];
for(int t=0;t<4;t++){
int x = i + ch[t][0], y = j + ch[t][1];
if(!check(x, y) || used[x][y]) continue;
used[x][y] = 1; sum += a[x][y];
mn = min(mn, a[x][y]), cnt++;
}
cntv++;
for(auto x : edges[i][j]){
if(used[x[0]][x[1]]) continue;
dfs(x[0], x[1]);
}
};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(used[i][j] || !is[i][j]) continue;
cnt = 0, cntv = 0, sum = 0, mn = 1e9;
dfs(i, j);
if(cnt < cntv * 3){
cout<<"No\n";
return;
}
res += sum;
if(cnt > cntv * 3) res -= mn;
}
}
cout<<res<<"\n";
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1;
//~ cin>>t;
while(t--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
4 ms |
1336 KB |
Output is correct |
3 |
Correct |
11 ms |
3812 KB |
Output is correct |
4 |
Correct |
33 ms |
10952 KB |
Output is correct |
5 |
Correct |
128 ms |
35708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
588 KB |
Output is correct |
3 |
Correct |
11 ms |
3788 KB |
Output is correct |
4 |
Correct |
32 ms |
10952 KB |
Output is correct |
5 |
Correct |
110 ms |
35716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
4 ms |
1356 KB |
Output is correct |
3 |
Correct |
11 ms |
3772 KB |
Output is correct |
4 |
Correct |
33 ms |
10960 KB |
Output is correct |
5 |
Correct |
106 ms |
35652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
6 ms |
2196 KB |
Output is correct |
4 |
Correct |
4 ms |
1356 KB |
Output is correct |
5 |
Correct |
11 ms |
4080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
4 ms |
1336 KB |
Output is correct |
3 |
Correct |
11 ms |
3812 KB |
Output is correct |
4 |
Correct |
33 ms |
10952 KB |
Output is correct |
5 |
Correct |
128 ms |
35708 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
3 ms |
588 KB |
Output is correct |
8 |
Correct |
11 ms |
3788 KB |
Output is correct |
9 |
Correct |
32 ms |
10952 KB |
Output is correct |
10 |
Correct |
110 ms |
35716 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
4 ms |
1356 KB |
Output is correct |
13 |
Correct |
11 ms |
3772 KB |
Output is correct |
14 |
Correct |
33 ms |
10960 KB |
Output is correct |
15 |
Correct |
106 ms |
35652 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
6 ms |
2196 KB |
Output is correct |
19 |
Correct |
4 ms |
1356 KB |
Output is correct |
20 |
Correct |
11 ms |
4080 KB |
Output is correct |
21 |
Correct |
2 ms |
588 KB |
Output is correct |
22 |
Correct |
4 ms |
1356 KB |
Output is correct |
23 |
Correct |
13 ms |
3812 KB |
Output is correct |
24 |
Correct |
37 ms |
10960 KB |
Output is correct |
25 |
Correct |
120 ms |
35704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
4 ms |
1336 KB |
Output is correct |
3 |
Correct |
11 ms |
3812 KB |
Output is correct |
4 |
Correct |
33 ms |
10952 KB |
Output is correct |
5 |
Correct |
128 ms |
35708 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
3 ms |
588 KB |
Output is correct |
8 |
Correct |
11 ms |
3788 KB |
Output is correct |
9 |
Correct |
32 ms |
10952 KB |
Output is correct |
10 |
Correct |
110 ms |
35716 KB |
Output is correct |
11 |
Correct |
2 ms |
588 KB |
Output is correct |
12 |
Correct |
4 ms |
1356 KB |
Output is correct |
13 |
Correct |
11 ms |
3772 KB |
Output is correct |
14 |
Correct |
33 ms |
10960 KB |
Output is correct |
15 |
Correct |
106 ms |
35652 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
6 ms |
2196 KB |
Output is correct |
19 |
Correct |
4 ms |
1356 KB |
Output is correct |
20 |
Correct |
11 ms |
4080 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
2 ms |
588 KB |
Output is correct |
27 |
Correct |
4 ms |
1356 KB |
Output is correct |
28 |
Correct |
13 ms |
3812 KB |
Output is correct |
29 |
Correct |
37 ms |
10960 KB |
Output is correct |
30 |
Correct |
120 ms |
35704 KB |
Output is correct |
31 |
Correct |
282 ms |
43892 KB |
Output is correct |
32 |
Correct |
110 ms |
35952 KB |
Output is correct |
33 |
Correct |
141 ms |
38616 KB |
Output is correct |
34 |
Correct |
119 ms |
35700 KB |
Output is correct |
35 |
Correct |
177 ms |
41064 KB |
Output is correct |