#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define PR(x) cerr << #x << "=" << (x) << endl;
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
const int N = 1000001;
int i, j, k, m, n;
int a[N];
int b[N], d[N], c[N];
vector<pii> v;
int clbest, clsum;
ll ans;
const int DX[]={-1,0,1,0,0};
const int DY[]={0,1,0,-1,0};
void nosol() {
cout << "No" << endl;
exit(0);
}
bool Empty(int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n) return 0;
return !c[x*n + y];
}
int GetA(int x, int y) {
return a[x*n + y];
}
void Set(int x, int y, int val) {
c[x*n + y] = val;
}
void Fill(int x, int y) {
Set(x, y, 1);
ans += GetA(x, y);
}
void DFS(int x, int y) {
F0(k, 4) {
int x2 = x + 2 * DX[k], y2 = y + 2 * DY[k];
if (Empty(x2, y2) && b[x2*n + y2]) {
Fill(x2, y2);
v.push_back(pii(x2, y2));
DFS(x2, y2);
}
}
}
void go(int at) {
if (at == SZ(v)) {
if (clsum > clbest) clbest = clsum;
return;
}
F0(k, 4) {
int sum = 0;
F0(dir, 4) if (dir != k) {
if (!Empty(v[at].first + DX[dir], v[at].second + DY[dir])) {
sum = -1; break;
} else sum += GetA(v[at].first + DX[dir], v[at].second + DY[dir]);
}
if (sum != -1) {
clsum += sum;
F0(dir, 4) if (dir != k) {
Set(v[at].first + DX[dir], v[at].second + DY[dir], 1);
}
go(at + 1);
F0(dir, 4) if (dir != k) {
Set(v[at].first + DX[dir], v[at].second + DY[dir], 0);
}
clsum -= sum;
}
}
}
int main() {
//freopen("x.in", "r", stdin);
cin >> m >> n;
F0(i, m * n) scanf("%d", &a[i]);
cin >> k;
while (k--) {
scanf("%d%d", &i, &j);
b[i*n+j] = 1;
}
// find pairs
F0(i, m) F0(j, n) if (b[i*n + j]) {
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) if (dx || dy) {
int i2 = i + dx, j2 = j + dy;
if (i2 < 0 || i2 >= m || j2 < 0 || j2 >= n || !b[i2*n + j2]) continue;
if (d[i*n + j] && d[i2*n + j2]) continue;
if (d[i*n + j] || d[i2*n + j2]) nosol();
d[i*n + j] = 1;
d[i2*n + j2] = 1;
F0(k, 5) if (!Empty(i + DX[k], j + DY[k])) nosol();
F0(k, 5) if (!Empty(i2 + DX[k], j2 + DY[k])) nosol();
F0(k, 5) if (Empty(i + DX[k], j + DY[k])) Fill(i + DX[k], j + DY[k]);
F0(k, 5) if (Empty(i2 + DX[k], j2 + DY[k])) Fill(i2 + DX[k], j2 + DY[k]);
}
}
}
F0(i, m) F0(j, n) if (b[i*n + j] && !d[i*n + j]) {
if (!Empty(i, j)) nosol();
int found = 0;
F0(k, 4) {
int good = 1;
F0(dir, 4) if (dir != k) {
if (!Empty(i + DX[dir], j + DY[dir])) {
good = 0;
break;
}
}
found = 1;
break;
}
if (!found) nosol();
}
F0(i, m) F0(j, n) if (b[i*n + j] && Empty(i, j)) {
v.clear();
v.push_back(pii(i, j));
Fill(i, j);
DFS(i, j);
for (pii p : v) {
//cerr << p.first << " " << p.second << endl;
}
clbest = -1;
go(0);
if (clbest == -1) nosol();
ans += clbest;
}
cout << ans << endl;
return 0;
}
Compilation message
covering.cpp: In function 'int main()':
covering.cpp:116:17: warning: variable 'good' set but not used [-Wunused-but-set-variable]
int good = 1;
^~~~
covering.cpp:134:18: warning: variable 'p' set but not used [-Wunused-but-set-variable]
for (pii p : v) {
^
covering.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
F0(i, m * n) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
covering.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &i, &j);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
9 ms |
768 KB |
Output is correct |
3 |
Correct |
17 ms |
1536 KB |
Output is correct |
4 |
Correct |
42 ms |
3704 KB |
Output is correct |
5 |
Correct |
130 ms |
10616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
8 ms |
640 KB |
Output is correct |
3 |
Correct |
17 ms |
1408 KB |
Output is correct |
4 |
Correct |
43 ms |
3832 KB |
Output is correct |
5 |
Correct |
133 ms |
10616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
9 ms |
768 KB |
Output is correct |
3 |
Correct |
17 ms |
1408 KB |
Output is correct |
4 |
Correct |
43 ms |
3704 KB |
Output is correct |
5 |
Correct |
141 ms |
10496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
11 ms |
896 KB |
Output is correct |
4 |
Correct |
9 ms |
640 KB |
Output is correct |
5 |
Correct |
17 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
9 ms |
768 KB |
Output is correct |
3 |
Correct |
17 ms |
1536 KB |
Output is correct |
4 |
Correct |
42 ms |
3704 KB |
Output is correct |
5 |
Correct |
130 ms |
10616 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
8 ms |
640 KB |
Output is correct |
8 |
Correct |
17 ms |
1408 KB |
Output is correct |
9 |
Correct |
43 ms |
3832 KB |
Output is correct |
10 |
Correct |
133 ms |
10616 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
9 ms |
768 KB |
Output is correct |
13 |
Correct |
17 ms |
1408 KB |
Output is correct |
14 |
Correct |
43 ms |
3704 KB |
Output is correct |
15 |
Correct |
141 ms |
10496 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
11 ms |
896 KB |
Output is correct |
19 |
Correct |
9 ms |
640 KB |
Output is correct |
20 |
Correct |
17 ms |
1280 KB |
Output is correct |
21 |
Correct |
7 ms |
512 KB |
Output is correct |
22 |
Correct |
8 ms |
768 KB |
Output is correct |
23 |
Correct |
18 ms |
1920 KB |
Output is correct |
24 |
Correct |
43 ms |
4728 KB |
Output is correct |
25 |
Correct |
130 ms |
14328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
512 KB |
Output is correct |
2 |
Correct |
9 ms |
768 KB |
Output is correct |
3 |
Correct |
17 ms |
1536 KB |
Output is correct |
4 |
Correct |
42 ms |
3704 KB |
Output is correct |
5 |
Correct |
130 ms |
10616 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
8 ms |
640 KB |
Output is correct |
8 |
Correct |
17 ms |
1408 KB |
Output is correct |
9 |
Correct |
43 ms |
3832 KB |
Output is correct |
10 |
Correct |
133 ms |
10616 KB |
Output is correct |
11 |
Correct |
6 ms |
512 KB |
Output is correct |
12 |
Correct |
9 ms |
768 KB |
Output is correct |
13 |
Correct |
17 ms |
1408 KB |
Output is correct |
14 |
Correct |
43 ms |
3704 KB |
Output is correct |
15 |
Correct |
141 ms |
10496 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
11 ms |
896 KB |
Output is correct |
19 |
Correct |
9 ms |
640 KB |
Output is correct |
20 |
Correct |
17 ms |
1280 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
5 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
5 ms |
384 KB |
Output is correct |
26 |
Correct |
7 ms |
512 KB |
Output is correct |
27 |
Correct |
8 ms |
768 KB |
Output is correct |
28 |
Correct |
18 ms |
1920 KB |
Output is correct |
29 |
Correct |
43 ms |
4728 KB |
Output is correct |
30 |
Correct |
130 ms |
14328 KB |
Output is correct |
31 |
Execution timed out |
1089 ms |
14960 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |