#include <bits/stdc++.h>
#include <random>
#ifndef LOCAL
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void solve();
mt19937_64 mt(1);
int32_t main() {
#ifdef LOCAL
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
//freopen("amusing.in", "r", stdin);
//freopen("amusing.out", "w", stdout);
#endif
cout << fixed << setprecision(30);
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}
}
pair<int, int> to[8] = {{2, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}, p[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool check(int i, int j, pair<int, int> s, vector<vector<int>>& a, vector<vector<int>>& used) {
return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y];
}
void dfs(int i, int j, vector<vector<int>>& a, vector<vector<int>>& used, multiset<int>& st, int& sz, int& sum) {
used[i][j] = 1;
sz++;
sum += a[i][j];
for (auto s : p) {
if (check(i, j, s, a, used)) {
st.insert(a[i + s.x][j + s.y]);
used[i + s.x][j + s.y] = 1;
sum += a[i + s.x][j + s.y];
}
}
for (auto s : to) {
if (check(i, j, s, a, used)) {
dfs(i + s.x, j + s.y, a, used, st, sz, sum);
}
}
}
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m)), used(n, vector<int>(m, 0));
int sz = 0, sum = 0;
multiset<int> st;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if (!((i + j) % 2)) {
used[i][j] = 1;
}
}
}
int k;
cin >> k;
ll res = 0;
vector<pair<int, int>> points(k);
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
points[i] = {x, y};
}
for (int i = 0; i < k; i++) {
used[points[i].x][points[i].y] = !used[points[i].x][points[i].y];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!((i + j) % 2) && !used[i][j]) {
dfs(i, j, a, used, st, sz, sum);
if (3 * sz > st.size()) {
cout << "No\n";
return;
}
while (3 * sz != st.size()) {
sum -= *st.begin();
st.erase(st.begin());
}
res += sum;
sz = 0;
sum = 0;
st.clear();
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((i + j) % 2) {
used[i][j] = 1;
} else {
used[i][j] = 0;
}
}
}
for (int i = 0; i < k; i++) {
used[points[i].x][points[i].y] = !used[points[i].x][points[i].y];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((i + j) % 2 && !used[i][j]) {
dfs(i, j, a, used, st, sz, sum);
if (3 * sz > st.size()) {
cout << "No\n";
return;
}
while (3 * sz != st.size()) {
sum -= *st.begin();
st.erase(st.begin());
}
res += sum;
sz = 0;
sum = 0;
st.clear();
}
}
}
cout << res << '\n';
}
Compilation message
covering.cpp: In function 'bool check(int, int, std::pair<int, int>, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
covering.cpp:45:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y];
| ~~~~~~~~^~~~~~~~~~
covering.cpp:45:74: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | return i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && !used[i + s.x][j + s.y];
| ~~~~~~~~^~~~~~~~~~~~~
covering.cpp: In function 'void solve()':
covering.cpp:96:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if (3 * sz > st.size()) {
| ~~~~~~~^~~~~~~~~~~
covering.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | while (3 * sz != st.size()) {
| ~~~~~~~^~~~~~~~~~~~
covering.cpp:127:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (3 * sz > st.size()) {
| ~~~~~~~^~~~~~~~~~~
covering.cpp:131:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | while (3 * sz != st.size()) {
| ~~~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
1628 KB |
Output is correct |
4 |
Correct |
16 ms |
3928 KB |
Output is correct |
5 |
Correct |
53 ms |
11920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
1628 KB |
Output is correct |
4 |
Correct |
19 ms |
3932 KB |
Output is correct |
5 |
Correct |
54 ms |
11932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
1624 KB |
Output is correct |
4 |
Correct |
17 ms |
3932 KB |
Output is correct |
5 |
Correct |
53 ms |
12056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
3 ms |
860 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
6 ms |
1872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
1628 KB |
Output is correct |
4 |
Correct |
16 ms |
3928 KB |
Output is correct |
5 |
Correct |
53 ms |
11920 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
6 ms |
1628 KB |
Output is correct |
9 |
Correct |
19 ms |
3932 KB |
Output is correct |
10 |
Correct |
54 ms |
11932 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
6 ms |
1624 KB |
Output is correct |
14 |
Correct |
17 ms |
3932 KB |
Output is correct |
15 |
Correct |
53 ms |
12056 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
464 KB |
Output is correct |
18 |
Correct |
3 ms |
860 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
6 ms |
1872 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
2 ms |
976 KB |
Output is correct |
23 |
Correct |
6 ms |
1636 KB |
Output is correct |
24 |
Correct |
17 ms |
3928 KB |
Output is correct |
25 |
Correct |
53 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
1628 KB |
Output is correct |
4 |
Correct |
16 ms |
3928 KB |
Output is correct |
5 |
Correct |
53 ms |
11920 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
6 ms |
1628 KB |
Output is correct |
9 |
Correct |
19 ms |
3932 KB |
Output is correct |
10 |
Correct |
54 ms |
11932 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
6 ms |
1624 KB |
Output is correct |
14 |
Correct |
17 ms |
3932 KB |
Output is correct |
15 |
Correct |
53 ms |
12056 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
464 KB |
Output is correct |
18 |
Correct |
3 ms |
860 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
6 ms |
1872 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
2 ms |
976 KB |
Output is correct |
28 |
Correct |
6 ms |
1636 KB |
Output is correct |
29 |
Correct |
17 ms |
3928 KB |
Output is correct |
30 |
Correct |
53 ms |
12116 KB |
Output is correct |
31 |
Correct |
222 ms |
27792 KB |
Output is correct |
32 |
Correct |
54 ms |
13392 KB |
Output is correct |
33 |
Correct |
68 ms |
16068 KB |
Output is correct |
34 |
Correct |
57 ms |
13140 KB |
Output is correct |
35 |
Correct |
117 ms |
27024 KB |
Output is correct |