This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define tol(bi) (1LL<<((int)(bi)))
int32_t main(){
int h,w;
cin>>h>>w;
vector<vector<int>> val(h,vector<int>(w));
for (int i = 0; i < h; ++i)
{
for (int j = 0; j < w; j++){
cin>>val[i][j];
}
}
int n;cin>>n;
vector<vector<int>> arr(h,vector<int>(w,0));
vector<pair<int,int>> spec(n);
for (int i = 0; i < n; i++){
int x,y;cin>>x>>y;
arr[x][y]=i+1;
spec[i]={x,y};
}
vector<bool> vis(n,false);
int ans=0;
function<int(int)> dfs;
function<void(int,int)> dallan;
vector<int> crvis(n,false);
set<int> st;
dallan = [&](int x, int y)->void{
if (x>0 && arr[x-1][y]>0) {
st.insert(arr[x-1][y]-1);
}
if (x+1<h && arr[x+1][y]>0) {
st.insert(arr[x+1][y]-1);
}
if (y>0 && arr[x][y-1]>0) {
st.insert(arr[x][y-1]-1);
}
if (y+1<w && arr[x][y+1]>0) {
st.insert(arr[x][y+1]-1);
}
};
dfs = [&](int node)->int{
vis[node]=true;
if (crvis[node]) return 0;
crvis[node]=true;
int x = spec[node].first;
int y = spec[node].second;
vector<pair<int,int>> ava;
set<int> crset;
if (x>0) dallan(x-1,y);
if (y>0) dallan(x,y-1);
if (x+1<h) dallan(x+1,y);
if (y+1<w) dallan(x,y+1);
dallan(x,y);
swap(crset,st);
if (x>0 && arr[x-1][y]==0) ava.push_back({x-1,y});
if (y>0 && arr[x][y-1]==0) ava.push_back({x,y-1});
if (x+1<h && arr[x+1][y]==0) ava.push_back({x+1,y});
if (y+1<w && arr[x][y+1]==0) ava.push_back({x,y+1});
if (ava.size()<3){
crvis[node]=false;
return -1;
}
int rval = -1;
for (int i = 0; i <= ava.size(); i++){
int cnt = 0;
for (int j = 0; j < ava.size(); j++){
if (i==j) continue;
cnt++;
}
if (cnt!=3) continue;
int crr = 0;
for (int j = 0; j < ava.size(); j++){
if (i==j) continue;
arr[ava[j].first][ava[j].second]=-23;
crr+=val[ava[j].first][ava[j].second];
}
for (auto it : crset){
int crrr=dfs(it);
if (crrr==-1){
crr=-1;
break;
}
else{
crr+=crrr;
}
}
for (int j = 0; j < ava.size(); j++){
if (i==j) continue;
arr[ava[j].first][ava[j].second]=0;
}
if (crr!=-1) rval=max(rval,crr);
}
crvis[node]=false;
if (rval==-1) return rval;
return rval+val[x][y];
};
for (int i = 0; i < n; i++){
if (vis[i]) continue;
int rval = dfs(i);
if (rval==-1){
ans=-1;
break;
}
else {
ans+=rval;
}
}
if (ans==-1){
cout<<"No"<<endl;
}
else cout<<ans<<endl;
}
Compilation message (stderr)
covering.cpp: In lambda function:
covering.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int i = 0; i <= ava.size(); i++){
| ~~^~~~~~~~~~~~~
covering.cpp:68:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int j = 0; j < ava.size(); j++){
| ~~^~~~~~~~~~~~
covering.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int j = 0; j < ava.size(); j++){
| ~~^~~~~~~~~~~~
covering.cpp:89:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j = 0; j < ava.size(); j++){
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |