#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
ll n,m;
ll check(ll x1,ll y1,vector<vector<bool>>& cen,vector<vector<ll>>& a){
multiset<ll> cands,noncands;
ll ret = 0,nbc = 0,nb = 0;
deque<pair<ll,ll>> q;
q.emplace_back(x1,y1);
cen[x1][y1] = false;
while(!q.empty()){
ll x,y;
tie(x,y) = q.front();
q.pop_front();
++nbc;
if(a[x][y] < 0) return -inf;
a[x][y] = -inf;
for(ll i = max(0ll,x-1); i <= min(m-1,x+1); ++i){
for(ll j = max(0ll,y-1); j <= min(n-1,y+1); ++j){
if(a[i][j] >= 0){
cands.emplace(a[i][j]);
ret += a[i][j];
a[i][j] = -inf;
++nb;
}
}
}
if(x >= 2 and cen[x-2][y]){
cen[x-2][y] = false;
if(a[x-1][y] >= 0) noncands.emplace(a[x-1][y]);
q.emplace_back(x-2,y);
}
if(x < m-2 and cen[x+2][y]){
cen[x+2][y] = false;
if(a[x+1][y] >= 0) noncands.emplace(a[x+1][y]);
q.emplace_back(x+2,y);
}
if(y >= 2 and cen[x][y-2]){
cen[x][y-2] = false;
if(a[x][y-1] >= 0) noncands.emplace(a[x][y-1]);
q.emplace_back(x,y-2);
}
if(y < n-2 and cen[x][y+2]){
cen[x][y+2] = false;
if(a[x][y+1] >= 0) noncands.emplace(a[x][y+1]);
q.emplace_back(x,y+2);
}
}
if(nb < 3*nbc) return -inf;
if(nb == 3*nbc) return ret;
for(ll i : noncands) cands.erase(cands.find(i));
ll val = inf;
for(ll i : cands) val = min(val,i);
return ret-val;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll k,x,y;
cin >> m >> n;
vector<vector<ll>> a(m,vector<ll>(n));
for(ll i = 0; i < m; ++i){
for(ll j = 0; j < n; ++j) cin >> a[i][j];
}
vector<vector<bool>> cen(m,vector<bool>(n));
cin >> k;
vector<pair<ll,ll>> vp;
for(ll i = 0; i < k; ++i){
cin >> x >> y;
cen[x][y] = true;
vp.emplace_back(x,y);
}
for(auto& p : vp){
tie(x,y) = p;
ll cnt = 0,tot = 0;
for(ll i = max(0ll,x-1); i <= min(m-1,x+1); ++i){
for(ll j = max(0ll,y-1); j <= min(n-1,y+1); ++j){
if(cen[i][j]) ++cnt;
++tot;
}
}
if(cnt >= 3 or (tot <= 6 and cnt >= 2) or tot <= 4){
cout << "No";
return 0;
}
}
ll ans = 0;
vector<pair<ll,ll>> vp2;
for(auto& p : vp){
tie(x,y) = p;
if(0 < x and x < m-1 and 0 < y and y < n-1){
if(cen[x-1][y-1] or cen[x-1][y] or cen[x-1][y+1]){
if(a[x][y-1] < 0 or a[x][y] < 0 or a[x][y+1] < 0 or a[x+1][y] < 0){
cout << "No";
return 0;
}
ans += a[x][y-1]+a[x][y+1]+a[x+1][y];
a[x][y-1] = a[x][y] = a[x][y+1] = a[x+1][y] = -inf;
}
else if(cen[x+1][y-1] or cen[x+1][y] or cen[x+1][y+1]){
if(a[x][y-1] < 0 or a[x][y] < 0 or a[x][y+1] < 0 or a[x-1][y] < 0){
cout << "No";
return 0;
}
ans += a[x][y-1]+a[x][y+1]+a[x-1][y];
a[x][y-1] = a[x][y] = a[x][y+1] = a[x-1][y] = -inf;
}
else if(cen[x][y-1]){
if(a[x-1][y] < 0 or a[x][y] < 0 or a[x+1][y] < 0 or a[x][y+1] < 0){
cout << "No";
return 0;
}
ans += a[x-1][y]+a[x+1][y]+a[x][y+1];
a[x-1][y] = a[x][y] = a[x+1][y] = a[x][y+1] = -inf;
}
else if(cen[x][y+1]){
if(a[x-1][y] < 0 or a[x][y] < 0 or a[x+1][y] < 0 or a[x][y-1] < 0){
cout << "No";
return 0;
}
ans += a[x-1][y]+a[x+1][y]+a[x][y-1];
a[x-1][y] = a[x][y] = a[x+1][y] = a[x][y-1] = -inf;
}
else vp2.emplace_back(x,y);
}
else{
if(a[x][y] < 0){
cout << "No";
return 0;
}
a[x][y] = -inf;
if(x > 0 and a[x-1][y] >= 0){
ans += a[x-1][y];
a[x-1][y] = -inf;
}
if(x < m-1 and a[x+1][y] >= 0){
ans += a[x+1][y];
a[x+1][y] = -inf;
}
if(y > 0 and a[x][y-1] >= 0){
ans += a[x][y-1];
a[x][y-1] = -inf;
}
if(y < n-1 and a[x][y+1] >= 0){
ans += a[x][y+1];
a[x][y+1] = -inf;
}
}
}
vector<vector<bool>> cen2(m,vector<bool>(n));
for(auto& p : vp2){
tie(x,y) = p;
cen2[x][y] = true;
}
for(auto& p : vp2){
tie(x,y) = p;
if(cen2[x][y]){
ll tmp = check(x,y,cen2,a);
if(tmp < 0){
cout << "No";
return 0;
}
ans += tmp;
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
