using namespace std;
#include <iostream>
#include <vector>
#include <map>
#include <limits>
vector<vector<int>> num;
vector<vector<bool>> pain;
long long sum;
int n, m, k;
unsigned int mini = (int)-1;
vector<vector<bool>> blue;
map <pair<int, int>, bool> vis;
vector<pair<int, int>> vis1;
/*bool put(int i, int j, int d) {
if (i == 0 && d != 4) {
return 0;
}
if (i == m - 1 && d != 2) {
return 0;
}
if (j == 0 && d != 1) {
return 0;
}
if (j == n - 1 && d != 3) {
return 0;
}
sum += num[i][j];
cot[i][j] = 1;
if (d % 2 == 1) {
cot[i + 1][j] = 1;
cot[i - 1][j] = 1;
sum += num[i + 1][j];
sum += num[i - 1][j];
}
else {
cot[i][j + 1] = 1;
cot[i][j - 1] = 1;
sum += num[i][j + 1];
sum += num[i][j - 1];
if (d == 2) {
sum += num[i - 1][j];
cot[i - 1][j] = 1;
}
}
}*/
bool markBlue(int i, int j) {
if (i < 0 || j < 0 || i >= m || j >= n || pain[i][j] || blue[i][j]) {
return false;
}
blue[i][j] = true;
if (num[i][j] < mini)
mini = num[i][j];
sum += num[i][j];
return true;
}
bool check(int i, int j) {
return !(i < 0 || j < 0 || i >= m || j >= n);
}
bool add(vector<pair<int, int>>& nut, int x, int y) {
if (check(x, y) && pain[x][y] && !vis[{x, y}]) {
nut.push_back({ x,y });
vis[{x, y}] = 1;
return true;
}
return false;
}
int main()
{
cin >> m;
cin >> n;
sum = 0;
pain.resize(m);
num.resize(m);
blue.resize(m);
for (int i = 0; i < m; i++) {
pain[i].resize(n);
for (int j = 0; j < n; j++) {
int x;
cin >> x;
num[i].push_back(x);
blue[i].push_back(0);
}
}
cin >> k;
pair<int, int> rand;
for (int i = 0; i < k; i++) {
int x, y;
cin >> x;
cin >> y;
vis[{ x, y }] = 0;
vis1.push_back({ x,y });
pain[x][y] = 1;
rand = { x,y };
}
int blues = 0, reds = 1;
bool flag = true;
vector<pair<int, int>> nut;
for (int i = 0; i < k; i++) {
if (vis[vis1[i]])
continue;
nut.push_back(vis1[i]);
vis[vis1[i]] = 1;
while (nut.size() != 0) {
int x = nut[nut.size() - 1].first, y = nut[nut.size() - 1].second;
nut.pop_back();
blues += markBlue(x - 1, y);
blues += markBlue(x, y - 1);
blues += markBlue(x + 1, y);
blues += markBlue(x, y + 1);
reds += add(nut, x - 2, y);
reds += add(nut, x - 1, y);
reds += add(nut, x + 1, y);
reds += add(nut, x + 2, y);
reds += add(nut, x - 1, y - 1);
reds += add(nut, x - 1, y + 1);
reds += add(nut, x + 1, y - 1);
reds += add(nut, x + 1, y + 1);
reds += add(nut, x, y - 2);
reds += add(nut, x, y - 1);
reds += add(nut, x, y + 1);
reds += add(nut, x, y + 2);
sum += num[x][y];
}
if (reds * 3 > blues) {
cout << "No";
flag = false;
break;
}
if (reds * 3 + 1 == blues) {
sum -= mini;
}
mini = (int)-1;
blues = 0;
reds = 1;
}
if (flag)
cout << sum;
}
Compilation message
covering.cpp: In function 'bool markBlue(int, int)':
covering.cpp:54:19: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'unsigned int' [-Wsign-compare]
54 | if (num[i][j] < mini)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
508 KB |
Output is correct |
3 |
Correct |
26 ms |
1120 KB |
Output is correct |
4 |
Correct |
82 ms |
3044 KB |
Output is correct |
5 |
Correct |
274 ms |
8496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
10 ms |
588 KB |
Output is correct |
3 |
Correct |
28 ms |
1068 KB |
Output is correct |
4 |
Correct |
80 ms |
3036 KB |
Output is correct |
5 |
Correct |
266 ms |
8512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
556 KB |
Output is correct |
3 |
Correct |
27 ms |
1108 KB |
Output is correct |
4 |
Correct |
82 ms |
3140 KB |
Output is correct |
5 |
Correct |
259 ms |
8568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
14 ms |
716 KB |
Output is correct |
4 |
Correct |
9 ms |
556 KB |
Output is correct |
5 |
Correct |
33 ms |
1164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
508 KB |
Output is correct |
3 |
Correct |
26 ms |
1120 KB |
Output is correct |
4 |
Correct |
82 ms |
3044 KB |
Output is correct |
5 |
Correct |
274 ms |
8496 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
588 KB |
Output is correct |
8 |
Correct |
28 ms |
1068 KB |
Output is correct |
9 |
Correct |
80 ms |
3036 KB |
Output is correct |
10 |
Correct |
266 ms |
8512 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
9 ms |
556 KB |
Output is correct |
13 |
Correct |
27 ms |
1108 KB |
Output is correct |
14 |
Correct |
82 ms |
3140 KB |
Output is correct |
15 |
Correct |
259 ms |
8568 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
296 KB |
Output is correct |
18 |
Correct |
14 ms |
716 KB |
Output is correct |
19 |
Correct |
9 ms |
556 KB |
Output is correct |
20 |
Correct |
33 ms |
1164 KB |
Output is correct |
21 |
Correct |
4 ms |
332 KB |
Output is correct |
22 |
Correct |
9 ms |
588 KB |
Output is correct |
23 |
Correct |
27 ms |
1148 KB |
Output is correct |
24 |
Correct |
78 ms |
3124 KB |
Output is correct |
25 |
Correct |
264 ms |
8688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
332 KB |
Output is correct |
2 |
Correct |
9 ms |
508 KB |
Output is correct |
3 |
Correct |
26 ms |
1120 KB |
Output is correct |
4 |
Correct |
82 ms |
3044 KB |
Output is correct |
5 |
Correct |
274 ms |
8496 KB |
Output is correct |
6 |
Correct |
3 ms |
332 KB |
Output is correct |
7 |
Correct |
10 ms |
588 KB |
Output is correct |
8 |
Correct |
28 ms |
1068 KB |
Output is correct |
9 |
Correct |
80 ms |
3036 KB |
Output is correct |
10 |
Correct |
266 ms |
8512 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
9 ms |
556 KB |
Output is correct |
13 |
Correct |
27 ms |
1108 KB |
Output is correct |
14 |
Correct |
82 ms |
3140 KB |
Output is correct |
15 |
Correct |
259 ms |
8568 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
296 KB |
Output is correct |
18 |
Correct |
14 ms |
716 KB |
Output is correct |
19 |
Correct |
9 ms |
556 KB |
Output is correct |
20 |
Correct |
33 ms |
1164 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
0 ms |
204 KB |
Output is correct |
24 |
Correct |
0 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
4 ms |
332 KB |
Output is correct |
27 |
Correct |
9 ms |
588 KB |
Output is correct |
28 |
Correct |
27 ms |
1148 KB |
Output is correct |
29 |
Correct |
78 ms |
3124 KB |
Output is correct |
30 |
Correct |
264 ms |
8688 KB |
Output is correct |
31 |
Correct |
644 ms |
19640 KB |
Output is correct |
32 |
Correct |
259 ms |
9404 KB |
Output is correct |
33 |
Correct |
280 ms |
13340 KB |
Output is correct |
34 |
Correct |
259 ms |
9412 KB |
Output is correct |
35 |
Correct |
349 ms |
12396 KB |
Output is correct |