제출 #466212

#제출 시각아이디문제언어결과실행 시간메모리
466212Tenis0206T-Covering (eJOI19_covering)C++11
25 / 100
280 ms11720 KiB
#include <bits/stdc++.h> using namespace std; int dx[] = {0,0,1,-1,1,-1,1,-1}; int dy[] = {1,-1,0,0,1,-1,-1,1}; vector<pair<int,int>> grupa; vector<vector<pair<int,int>>> gr; int n,m,k,a[1005][1005],sp[1005][1005]; bool sel[1005][1005]; void Fill(int x, int y) { grupa.push_back({x,y}); sp[x][y] = false; for(int p=0;p<8;p++) { int xx = x + dx[p]; int yy = y + dy[p]; if(sp[xx][yy]) { Fill(xx,yy); } } } void bordare() { for(int i=0;i<=n+1;i++) { sel[i][0] = sel[i][m+1] = true; } for(int i=0;i<=m+1;i++) { sel[0][i] = sel[n+1][i] = true; } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } bordare(); cin>>k; for(int i=1;i<=k;i++) { int x,y; cin>>x>>y; ++x; ++y; sp[x][y] = true; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!sp[i][j]) { continue; } grupa.clear(); Fill(i,j); if(grupa.size()>2) { cout<<"No"<<'\n'; return 0; } gr.push_back(grupa); } } long long sum = 0; for(auto v : gr) { if(v.size()==1) { continue; } pair<int,int> x = v[0]; pair<int,int> y = v[1]; if(x.first==y.first) { if(x.second>y.second) { swap(x,y); } int i = x.first; int j = x.second; if(sel[i][j] || sel[i][j-1] || sel[i-1][j] || sel[i+1][j] || sel[i][j+1] || sel[i][j+2] || sel[i-1][j+1] || sel[i+1][j+1]) { cout<<"No"<<'\n'; return 0; } sum += (a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+1] + a[i+1][j+1]); sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = sel[i][j+1] = sel[i][j+2] = sel[i-1][j+1] = sel[i+1][j+1] = true; } else if(x.second==y.second) { if(x.first>y.first) { swap(x,y); } int i = x.first; int j = x.second; if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j] || sel[i+2][j] || sel[i+1][j-1] || sel[i+1][j+1]) { cout<<"No"<<'\n'; return 0; } sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j] + a[i+2][j] + a[i+1][j-1] + a[i+1][j+1]); sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j] = sel[i+2][j] = sel[i+1][j-1] = sel[i+1][j+1] = true; } else if((x.first<y.first && x.second<y.second) || (x.first>y.first && x.second>y.second)) { if(x.first>y.first) { swap(x,y); } int i = x.first; int j = x.second; if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j+1] || sel[i+2][j+1] || sel[i+1][j] || sel[i+1][j+2]) { cout<<"No"<<'\n'; return 0; } sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1] + a[i+1][j] + a[i+1][j+2]); sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j+1] = sel[i+2][j+1] = sel[i+1][j] = sel[i+1][j+2] = true; } else { if(x.first>y.first) { swap(x,y); } int i = x.first; int j = x.second; if(sel[i][j] || sel[i-1][j] || sel[i][j-1] || sel[i][j+1] || sel[i+1][j-1] || sel[i+2][j-1] || sel[i+1][j-2] || sel[i+1][j]) { cout<<"No"<<'\n'; return 0; } sum += (a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1] + a[i+1][j-1] + a[i+2][j-1] + a[i+1][j-2] + a[i+1][j]); sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = sel[i+1][j-1] = sel[i+2][j-1] = sel[i+1][j-2] = sel[i+1][j] = true; } } for(auto v : gr) { if(v.size()==2) { continue; } int i = v[0].first; int j = v[0].second; int Max = 0; if(!sel[i][j] && !sel[i+1][j] && !sel[i][j-1] && !sel[i][j+1]) { Max = max(Max,a[i][j] + a[i+1][j] + a[i][j-1] + a[i][j+1]); } if(!sel[i][j] && !sel[i-1][j] && !sel[i][j-1] && !sel[i][j+1]) { Max = max(Max,a[i][j] + a[i-1][j] + a[i][j-1] + a[i][j+1]); } if(!sel[i][j] && !sel[i][j+1] && !sel[i-1][j] && !sel[i+1][j]) { Max = max(Max,a[i][j] + a[i][j+1] + a[i-1][j] + a[i+1][j]); } if(!sel[i][j] && !sel[i][j-1] && !sel[i-1][j] && !sel[i+1][j]) { Max = max(Max,a[i][j] + a[i][j-1] + a[i-1][j] + a[i+1][j]); } if(!Max) { cout<<"No"<<'\n'; return 0; } if(Max==a[i][j]+a[i+1][j]+a[i][j-1]+a[i][j+1]) { sel[i][j] = sel[i+1][j] = sel[i][j-1] = sel[i][j+1] = true; } else if(Max==a[i][j]+a[i-1][j]+a[i][j-1]+a[i][j+1]) { sel[i][j] = sel[i-1][j] = sel[i][j-1] = sel[i][j+1] = true; } else if(Max==a[i][j]+a[i][j+1]+a[i-1][j]+a[i+1][j]) { sel[i][j] = sel[i][j+1] = sel[i-1][j] = sel[i+1][j] = true; } else if(Max==a[i][j]+a[i][j-1]+a[i-1][j]+a[i+1][j]) { sel[i][j] = sel[i][j-1] = sel[i-1][j] = sel[i+1][j] = true; } sum+=Max; } cout<<sum<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...