#include <bits/stdc++.h>
#define MN 717171
#define MM 1007171
#define INF 1000000000
using namespace std;
int n, m, k;
typedef pair<int, int> ii;
//vector<int> A[MN], B[MN];
vector<vector<int> > A, B;
bool V[MM];
deque<int> Nod;
vector<ii> Noduri;
int main() {
cin >> n >> m;
A.assign(n+2, vector<int>(m+2));
B.assign(n+2, vector<int>(m+2));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) cin >> A[i][j];
cin >> k;
vector<ii> C(k+2);
vector<vector<int> > L(k+2, vector<int>());
for(int i = 1; i <= k; ++i){
cin >> C[i].first >> C[i].second;
++C[i].first;
++C[i].second;
B[C[i].first][C[i].second] = i;
}
int VX[] = {-2, -1, -1, -1, 0, 0}; //12 / 2
int VY[] = {0, -1, 0, 1, -2, -1};
for(int i = 1; i <= k; ++i){
int ln, cn;
for(int d = 0; d < 6; ++d){
ln = C[i].first + VX[d];
cn = C[i].second + VY[d];
if(ln < 1 || cn < 1 || ln > n || cn > m || !B[ln][cn]) continue;
L[i].push_back(B[ln][cn]);
L[B[ln][cn]].push_back(i);
}
}
int DX[] = {-1, 0, 1, 0};
int DY[] = {0, 1, 0, -1};
int re = 0;
for(int i = 1; i <= k; ++i){
if(V[i]) continue;
V[i] = 1;
Nod.push_back(i);
int acum;
while(!Nod.empty()){
acum = Nod.front();
Nod.pop_front();
Noduri.push_back(C[acum]);
for(auto it : L[acum])
if(!V[it]){
V[it] = 1;
Nod.push_back(it);
}
}
set<ii> Vecini;
int ln, cn;
for(auto it : Noduri) {
re += A[it.first][it.second];
for(int d = 0; d < 4; ++d){
ln = it.first + DX[d];
cn = it.second + DY[d];
if(ln < 1 || cn < 1 || ln > n || cn > m || B[ln][cn])continue;
Vecini.insert({ln, cn});
}
}
for(auto it : Noduri)
Vecini.erase(it);
if(Vecini.size() < Noduri.size() * 3){
cout << "No\n";
return 0;
} else if(Vecini.size() == Noduri.size() * 3){
for(auto it : Vecini)
re += A[it.first][it.second];
} else {
int mi = INF;
for(auto it : Vecini){
re += A[it.first][it.second];
mi = min(mi, A[it.first][it.second]);
}
re -= mi;
}
Noduri.clear();
while(!Nod.empty())Nod.pop_back();
}
cout << re << "\n";
return 0;
}
# |
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 |
1592 KB |
Output is correct |
4 |
Correct |
82 ms |
3828 KB |
Output is correct |
5 |
Correct |
254 ms |
12024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
312 KB |
Output is correct |
2 |
Correct |
8 ms |
588 KB |
Output is correct |
3 |
Correct |
26 ms |
1476 KB |
Output is correct |
4 |
Correct |
79 ms |
3840 KB |
Output is correct |
5 |
Correct |
251 ms |
11972 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 |
27 ms |
1468 KB |
Output is correct |
4 |
Correct |
77 ms |
3828 KB |
Output is correct |
5 |
Correct |
290 ms |
12040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
14 ms |
972 KB |
Output is correct |
4 |
Correct |
9 ms |
712 KB |
Output is correct |
5 |
Correct |
28 ms |
1640 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 |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 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 |
1592 KB |
Output is correct |
4 |
Correct |
82 ms |
3828 KB |
Output is correct |
5 |
Correct |
254 ms |
12024 KB |
Output is correct |
6 |
Correct |
3 ms |
312 KB |
Output is correct |
7 |
Correct |
8 ms |
588 KB |
Output is correct |
8 |
Correct |
26 ms |
1476 KB |
Output is correct |
9 |
Correct |
79 ms |
3840 KB |
Output is correct |
10 |
Correct |
251 ms |
11972 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
588 KB |
Output is correct |
13 |
Correct |
27 ms |
1468 KB |
Output is correct |
14 |
Correct |
77 ms |
3828 KB |
Output is correct |
15 |
Correct |
290 ms |
12040 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
14 ms |
972 KB |
Output is correct |
19 |
Correct |
9 ms |
712 KB |
Output is correct |
20 |
Correct |
28 ms |
1640 KB |
Output is correct |
21 |
Correct |
4 ms |
312 KB |
Output is correct |
22 |
Correct |
8 ms |
672 KB |
Output is correct |
23 |
Correct |
28 ms |
1452 KB |
Output is correct |
24 |
Correct |
77 ms |
3828 KB |
Output is correct |
25 |
Correct |
261 ms |
12024 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 |
1592 KB |
Output is correct |
4 |
Correct |
82 ms |
3828 KB |
Output is correct |
5 |
Correct |
254 ms |
12024 KB |
Output is correct |
6 |
Correct |
3 ms |
312 KB |
Output is correct |
7 |
Correct |
8 ms |
588 KB |
Output is correct |
8 |
Correct |
26 ms |
1476 KB |
Output is correct |
9 |
Correct |
79 ms |
3840 KB |
Output is correct |
10 |
Correct |
251 ms |
11972 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
588 KB |
Output is correct |
13 |
Correct |
27 ms |
1468 KB |
Output is correct |
14 |
Correct |
77 ms |
3828 KB |
Output is correct |
15 |
Correct |
290 ms |
12040 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
308 KB |
Output is correct |
18 |
Correct |
14 ms |
972 KB |
Output is correct |
19 |
Correct |
9 ms |
712 KB |
Output is correct |
20 |
Correct |
28 ms |
1640 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
4 ms |
312 KB |
Output is correct |
27 |
Correct |
8 ms |
672 KB |
Output is correct |
28 |
Correct |
28 ms |
1452 KB |
Output is correct |
29 |
Correct |
77 ms |
3828 KB |
Output is correct |
30 |
Correct |
261 ms |
12024 KB |
Output is correct |
31 |
Correct |
642 ms |
30292 KB |
Output is correct |
32 |
Correct |
275 ms |
13052 KB |
Output is correct |
33 |
Correct |
269 ms |
15872 KB |
Output is correct |
34 |
Correct |
279 ms |
13032 KB |
Output is correct |
35 |
Correct |
342 ms |
23064 KB |
Output is correct |