#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
#define loop(i,a,b) for (int i = a; i <= b; i++)
#define INF ((unsigned) ~0)
#define F first
#define S second
#define PB push_back
#define MP make_pair
int m, n, k;
ll res;
int a[1000000];
map<pi, int> sp;
int getA(int r, int c){
if(n * r + c >= 0 && n * r + c < m * n)
return a[n * r + c];
return -1;
}
int& getAp(int r, int c){
if(n * r + c >= 0 && n * r + c < m * n)
return a[n * r + c];
int x = -1;
return x;
}
bool chkNgb(int r, int c){
if(n * r + c < 0 || n * r + c >= m * n)
return true;
if(sp.count(MP(r, c)) == 0)
return true;
if(sp[MP(r, c)] > 0)
return true;
int dn = 0;
if(getA(r + 1, c) == -1)
dn++;
if(getA(r - 1, c) == -1)
dn++;
if(getA(r, c + 1) == -1)
dn++;
if(getA(r, c - 1) == -1)
dn++;
if(dn >= 2)
return false;
if(dn == 1){
res += max(getA(r + 1, c), 0);
res += max(getA(r - 1, c), 0);
res += max(getA(r, c + 1), 0);
res += max(getA(r, c - 1), 0);
getAp(r + 1, c) = -1;
getAp(r - 1, c) = -1;
getAp(r, c + 1) = -1;
getAp(r, c - 1) = -1;
sp[MP(r, c)] = 1;
return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
}
if(sp.count(MP(r + 1, c + 1)) > 0){
res += max(getA(r + 1, c), 0);
res += max(getA(r - 1, c), 0);
res += max(getA(r, c - 1), 0);
getAp(r + 1, c) = -1;
getAp(r - 1, c) = -1;
getAp(r, c - 1) = -1;
sp[MP(r, c)] = 1;
return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
}
if(sp.count(MP(r - 1, c + 1)) > 0){
res += max(getA(r + 1, c), 0);
res += max(getA(r - 1, c), 0);
res += max(getA(r, c - 1), 0);
getAp(r + 1, c) = -1;
getAp(r - 1, c) = -1;
getAp(r, c - 1) = -1;
sp[MP(r, c)] = 1;
return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
}
if(sp.count(MP(r + 1, c - 1)) > 0){
res += max(getA(r + 1, c), 0);
res += max(getA(r - 1, c), 0);
res += max(getA(r, c + 1), 0);
getAp(r + 1, c) = -1;
getAp(r - 1, c) = -1;
getAp(r, c + 1) = -1;
sp[MP(r, c)] = 1;
return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
}
if(sp.count(MP(r - 1, c - 1)) > 0){
res += max(getA(r + 1, c), 0);
res += max(getA(r - 1, c), 0);
res += max(getA(r, c + 1), 0);
getAp(r + 1, c) = -1;
getAp(r - 1, c) = -1;
getAp(r, c + 1) = -1;
sp[MP(r, c)] = 1;
return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2);
}
return true;
}
pi dfs(int r, int c, int pr, int pc){
if(n * r + c < 0 || n * r + c >= m * n || sp.count(MP(r, c)) == 0)
return MP(0, 1001);
if(sp[MP(r, c)] == 2){
return MP(1, 1001);
}
sp[MP(r, c)] = 2;
pi s = MP(0, 1001);
for(int i = -1; i < 2; i += 2){
for(int j = -1; j < 2; j += 2){
if((r + i + j) != pr || (c + i - j) != pc){
res += getA(r + (i + j)/2, c + (i - j)/2);
//cout << r + (i + j)/2 << " " << c + (i - j)/2 << ":" << getA(r + (i + j)/2, c + (i - j)/2) << "\n";
s.S = min(s.S, getA(r + (i + j)/2, c + (i - j)/2));
pi p = dfs(r + i + j, c + i - j, r, c);
s = MP(max(s.F, p.F), min(s.S, p.S));
}
}
}
return s;
}
int main(){
res = 0;
cin >> m >> n;
for(int r = 0; r < m; r++)
for(int c = 0; c < n; c++)
cin >> a[n * r + c];
cin >> k;
for(int i = 0; i < k; i++){
int r, c;
cin >> r >> c;
sp[MP(r, c)] = 0;
res += a[n * r + c];
a[n * r + c] = -1;
}
for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){
if(!chkNgb((it->F).F, (it->F).S)){
cout << "No\n";
return 0;
}
}
//cout << res << "\n";
for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){
int r = (it->F).F;
int c = (it->F).S;
if(sp[MP(r, c)] == 0){
pi p = dfs(r, c, -1, -1);
//cout << p.S << "\n";
if(p.F == 0)
res -= p.S;
}
}
cout << res << "\n";
}
Compilation message
covering.cpp: In function 'int& getAp(int, int)':
covering.cpp:36:9: warning: reference to local variable 'x' returned [-Wreturn-local-addr]
int x = -1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
21 ms |
768 KB |
Output is correct |
| 4 |
Correct |
15 ms |
640 KB |
Output is correct |
| 5 |
Correct |
37 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
